Jest na to jakieś proste sprawdzenie. Mam sobie jakiś tam graf. Powiedzmy, że mam taki graf:
Kwadrat, kwadrat bez bocznej ściany i linię prostą. Każdy z tych grafów ma 4 węzły w1,w2,w3,w4 .
Który z tych grafów jest drzewem i dlaczego ?
Kiedy o grafie powiemy, że jest drzewem ?
-
Kmitah
- Użytkownik
- Posty: 179
- Rejestracja: 16 lut 2012, o 16:34
- Płeć: Mężczyzna
- Lokalizacja: Suwałki / Białystok
- Podziękował: 23 razy
- Pomógł: 28 razy
Kiedy o grafie powiemy, że jest drzewem ?
Jest wiele różnych charakteryzacji drzewa. Na przykład:
Graf \(\displaystyle{ G}\) jest drzewem \(\displaystyle{ \Leftrightarrow}\) \(\displaystyle{ G}\) jest grafem spójnym bez cykli \(\displaystyle{ \Leftrightarrow}\) \(\displaystyle{ G}\) jest grafem spójnym o \(\displaystyle{ n}\) wierzchołkach i \(\displaystyle{ n-1}\) krawędziach \(\displaystyle{ \Leftrightarrow}\) dowolne dwa wierzchołki grafu \(\displaystyle{ G}\) da się połączyć dokładnie jedną drogą.
W Twoim przykładzie, drzewem jest graf trzeci oraz graf drugi, jeżeli przez "kwadrat bez bocznej ściany" rozumiesz "kwadrat bez bocznej ściany i przekątnych", natomiast "cały" kwadrat nie jest drzewem, nieważne czy z przekątnymi czy bez, ponieważ pojawia się cykl.
Graf \(\displaystyle{ G}\) jest drzewem \(\displaystyle{ \Leftrightarrow}\) \(\displaystyle{ G}\) jest grafem spójnym bez cykli \(\displaystyle{ \Leftrightarrow}\) \(\displaystyle{ G}\) jest grafem spójnym o \(\displaystyle{ n}\) wierzchołkach i \(\displaystyle{ n-1}\) krawędziach \(\displaystyle{ \Leftrightarrow}\) dowolne dwa wierzchołki grafu \(\displaystyle{ G}\) da się połączyć dokładnie jedną drogą.
W Twoim przykładzie, drzewem jest graf trzeci oraz graf drugi, jeżeli przez "kwadrat bez bocznej ściany" rozumiesz "kwadrat bez bocznej ściany i przekątnych", natomiast "cały" kwadrat nie jest drzewem, nieważne czy z przekątnymi czy bez, ponieważ pojawia się cykl.
Kiedy o grafie powiemy, że jest drzewem ?
Nie mieliśmy zajęciach pojęcia cyklu grafu, nie sprawdzaliśmy czegoś takiego jak spójność grafu.
A co dokładnie rozumieć przez : "da się połączyć dokładnie jedną drogą 2 wierzchołki"
jak np. od wierzchołka 3 do wierzchołka 4, istnieją 2 drogi to już taki graf nie może być drzewem ? I czy ten sens drzewa można rozumieć jako normalne drzewa BSD ?
A co dokładnie rozumieć przez : "da się połączyć dokładnie jedną drogą 2 wierzchołki"
jak np. od wierzchołka 3 do wierzchołka 4, istnieją 2 drogi to już taki graf nie może być drzewem ? I czy ten sens drzewa można rozumieć jako normalne drzewa BSD ?
-
Kmitah
- Użytkownik
- Posty: 179
- Rejestracja: 16 lut 2012, o 16:34
- Płeć: Mężczyzna
- Lokalizacja: Suwałki / Białystok
- Podziękował: 23 razy
- Pomógł: 28 razy
Kiedy o grafie powiemy, że jest drzewem ?
Drzewo BSD to szczególny typ drzewa, więc spełnia ono wszystkie twierdzenia matematyczne dotyczące drzew.
Tak, jeżeli od wierzchołka 3 do wierzchołka 4 istnieją dwie drogi, to wtedy nie jest już to drzewo.
'Spójność' oznacza, że graf jest "w jednym kawałku", nie składa się z kilku niepołączonych ze sobą części.
Tak, jeżeli od wierzchołka 3 do wierzchołka 4 istnieją dwie drogi, to wtedy nie jest już to drzewo.
'Spójność' oznacza, że graf jest "w jednym kawałku", nie składa się z kilku niepołączonych ze sobą części.
Kiedy o grafie powiemy, że jest drzewem ?
Skoro ma istnieć dokładnie tylko jedna droga to dlaczego zwykły kwadrat który nie ma niczego w środku nie jest drzewem ?
Listy sąsiedztwa dla niego wyglądają następująco:
w1->w2, w1->w3
w2->w4 , w4->w3
Dla wybranego przez Ciebie grafu nr 3, mamy: w1-> w2,w3,w4
w2->w1,w3,w4
w3->w2,w1,w4
w4->w1,w2,w3
Listy sąsiedztwa dla niego wyglądają następująco:
w1->w2, w1->w3
w2->w4 , w4->w3
Dla wybranego przez Ciebie grafu nr 3, mamy: w1-> w2,w3,w4
w2->w1,w3,w4
w3->w2,w1,w4
w4->w1,w2,w3
-
Kmitah
- Użytkownik
- Posty: 179
- Rejestracja: 16 lut 2012, o 16:34
- Płeć: Mężczyzna
- Lokalizacja: Suwałki / Białystok
- Podziękował: 23 razy
- Pomógł: 28 razy
Kiedy o grafie powiemy, że jest drzewem ?
Dla grafu "kwadratowego" ponumerujmy wierzchołki kolejno: (1), (2), (3), (4).
Z wierzchołka (1) do (4) możemy dojść na dwa sposoby. Drogą (1)->(2)->(4) lub drogą (1)->(3)->(4), zatem nie jest prawdą, iż dowolne dwa wierzchołki grafu można połączyć dokładnie jedną drogą, zatem nie jest prawdą, iż graf jest drzewem.
Z wierzchołka (1) do (4) możemy dojść na dwa sposoby. Drogą (1)->(2)->(4) lub drogą (1)->(3)->(4), zatem nie jest prawdą, iż dowolne dwa wierzchołki grafu można połączyć dokładnie jedną drogą, zatem nie jest prawdą, iż graf jest drzewem.