Udowodnić ze jeżeli graf ma n wierzcholkow
-
- 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
Udowodnić ze jeżeli graf jest drzewem o n wierzchołkach to ma n-1 krawedzi
- jutrvy
- 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
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.