szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 11 lip 2015, o 23:18 
Użytkownik

Posty: 541
Lokalizacja: Kielce
Witam,

Mam takie oto twierdzenie.

Graf jest 2-spójny wierzcholkowo wtw gdy każda para wiercholkow znajduje się w tym samym cyklu.

Nie za bardzo rozumiem co mówi to twierdzenie ani jak się za nie zabrać. Mogę prosić o pomoc?
Góra
Mężczyzna Offline
PostNapisane: 12 lip 2015, o 12:40 
Użytkownik

Posty: 59
Lokalizacja: Polska
Graf jest k-spójny (wierzchołkowo) wtedy, kiedy po usunięciu k-1 wierzchołków pozostaje spójny. Czyli w 2-spójnym usunięcie jednego wierzchołka nie powinno powodować rozspójnienia.

Graf jest spójny, kiedy dla dowolnej pary wierzchołków istnieje ścieżka, która je łączy.

Skoro nasz graf jest spójny, to istnieje ścieżka pomiędzy dowolną parą wierzchołków. Jest on również 2-spójny, więc po usunięciu pewnego wierzchołka (dowolnego, ale nie z naszej pary, bo wtedy dalsze rozważanie nie ma sensu) ścieżka pomiędzy wierzchołkami tamtej pary również istnieje. Jednak usunięty wierzchołek mógł być częścią jednej ze ścieżek pomiędzy wierzchołkami, a więc takich ścieżek przed usunięciem było dwie lub więcej (zbiory wierzchołków tych ścieżek muszą być rozłączne). Czyli mamy 2 rozłączne ścieżki (możemy z nich wybrać drogi) pomiędzy dwoma wierzchołkami, a więc istnieje cykl (z tychże dróg).
Góra
Mężczyzna Offline
PostNapisane: 12 lip 2015, o 15:50 
Użytkownik

Posty: 541
Lokalizacja: Kielce
Dlaczego te ścieżki muszą być rozlączne?
Góra
Mężczyzna Offline
PostNapisane: 12 lip 2015, o 18:44 
Użytkownik

Posty: 259
Lokalizacja: Polska
Może inaczej. Istnieją co najmniej dwie ścieżki. Gdyby pokazać, że co najmniej dwie z nich są rozłączne to mielibyśmy tezę. Ale przecież gdyby tak nie było, to wszystkie miałyby wspólną krawędź. Ale wówczas usunięcie jej spowodowałoby rozspójnienie grafu, czyli nie byłby 2-spójny.
Góra
Mężczyzna Offline
PostNapisane: 12 lip 2015, o 19:15 
Użytkownik

Posty: 541
Lokalizacja: Kielce
To co piszesz jest nieprawdziwe. To że nie są rozlacze wcale nie znaczy że wszystkie muszą łączyć się w pewnym wierzchołku

-- 12 lip 2015, o 19:23 --

Przepraszam pomyliłem się.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Czy graf k-krytyczne moze byc nieskonczony?  kingataranek  4
 czy istnieje graf o stopniach wierzchołków  anilahcim  2
 Czy graf jest eulerowski/hamiltonowski  De Moon  2
 Graf petersena  Ceplusplusik  1
 Oznaczenia grafów - jak narysować graf np. K3?  anusiakk  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl