Udowodnić ze jeżeli graf ma n wierzcholkow

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
czerwonepomidory
Użytkownik
Użytkownik
Posty: 13
Rejestracja: 21 paź 2016, o 15:41
Płeć: Kobieta
Lokalizacja: Warszawa
Podziękował: 6 razy

Udowodnić ze jeżeli graf ma n wierzcholkow

Post autor: czerwonepomidory »

Udowodnić ze jeżeli graf jest drzewem o n wierzchołkach to ma n-1 krawedzi
Awatar użytkownika
jutrvy
Użytkownik
Użytkownik
Posty: 1202
Rejestracja: 24 lis 2014, o 18:04
Płeć: Mężczyzna
Podziękował: 10 razy
Pomógł: 239 razy

Re: Udowodnić ze jeżeli graf ma n wierzcholkow

Post autor: jutrvy »

Indukcja po \(\displaystyle{ n}\). Jeśli masz drzewo o jednym wierzchołku, to ma zero krawędzi i twierdzenie jest prawdziwe. Weźmy drzewo o \(\displaystyle{ n+1}\) wierzchołkach i usuńmy z niego liść (wierzchołek stopnia jeden) wraz z krawędzią z nim incydentną. Zostało nam drzewo o \(\displaystyle{ n}\) wierzchołkach, które z założenia indukcyjnego ma \(\displaystyle{ n-1}\) krawędzi. Dodajemy usunięty wcześniej wierzchołek (wraz z krawędzią) i dostajemy, że nasze drzewo o \(\displaystyle{ n+1}\) wierzchołkach ma \(\displaystyle{ n}\) krawędzi. Twierdzenie zostało udowodnione.
ODPOWIEDZ