Grafy
Levi: Niech k,n ∊ ℕ:
a) ustal, dla jakich wartości n istnieje chociaż jeden graf rzędu n posiadający k wierzchołków
wiszących?
b) jaka jest maksymalna i minimalna liczba krawędzi w grafie rzędu n posiadającym k
wierzchołków wiszących?
proszę o wyjaśnienie
kochanus_niepospolitus:
a)
jeżeli n=k, to n∊N (po prostu masz same wierzchołki izolowane)
jeżeli n> k to n ≥ k+2 (aby istniały przynajmniej dwa wierzchołki, które możemy ze sobą
połączyć)
b)
minimalna: n−k−1
| | (n−k−1)*(n−k) | |
maksymalna: |
| (podgraf będący grałem Kn−k) |
| | 2 | |