szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
PostNapisane: 1 sie 2015, o 16:16 
Użytkownik
Jeśli graf G jest regularny, spójny, dwudzielny i ma co najmniej 3 wierzchołki to G jest dwuspójny.

Jedyne do czego doszedłem to to, że jeśli mamy graf regularny i dwudzielny to na pewno ma on skojarzenie doskonałe. To jednak nie implikuje tego,że jest dwuspójny.

Dwuspójność z kolei oznacza,że dla każdych dwóch różnych wierzchołków u,v istnieje cykl w grafie G taki,że te wierzchołki należą do tego cyklu.
Jakieś wskazówki? Pierwszą rzeczą jest to,że nie wiem czy tylko tymi przejściami sobie nie komplikuje życia.
Góra
Mężczyzna Offline
PostNapisane: 1 sie 2015, o 20:26 
Gość Specjalny
Avatar użytkownika

Posty: 4977
Lokalizacja: Kraków
Załóż nie wprost, że istnieje krawędź rozspajająca...
Góra
PostNapisane: 6 sie 2015, o 20:56 
Użytkownik
Załóżmy,że istnieje krawędź rozspajająca. Graf G jest dwudzielny więc (V=V_{1} \cup V_{2}) jeden z jej końców musi należeć do V_{1}a drugi do V_{2}.
Mamy więc dopiero 2wierzchołki (w założeniu co najmniej 3). Musi więc istnieć co najmniej 1sąsiad wierzchołka należącego do V_{1} lub V_{2}. Dodajmy więc wierzchołek do wybranej dowolnie klasy wierzchołków. To powoduje,że graf nie jest regularny więc należy dodać do już dodanego kolejny wierzchołek. Musi być on połączony z już istniejącymi. Mamy więc cykl,co przeczy temu,że istnieje krawędź rozspajająca. Proszę kogoś o sprawdzenie czy tok rozumowania właściwy,o formalizm się pomartwię później.
Góra
Mężczyzna Offline
PostNapisane: 7 sie 2015, o 08:51 
Gość Specjalny
Avatar użytkownika

Posty: 4977
Lokalizacja: Kraków
Nie jest właściwy.
Rozważ jeden z podgrafów powstałych po rozspojeniu.
Jest również dwudzielny. Rozważ obie strony dwudzielności i sumę stopni wierzchołków tamże.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Graf kostki 4 - wymiarowej  matwie  5
 Kolorówanie - graf dopełniony i zwykły  matinf  5
 Ile wierzchołków i krawędzi ma graf?  uczen23  1
 Udowodnij, że graf i jego dopełnienie nie mogą być planarne  emperor2  2
 Graf nieskonczony  Nesquik  6
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl