szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 1 sie 2015, o 17:16 
Użytkownik

Posty: 394
Lokalizacja: Warszawa
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.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 1 sie 2015, o 21:26 
Gość Specjalny
Avatar użytkownika

Posty: 4974
Lokalizacja: Lozanna
Załóż nie wprost, że istnieje krawędź rozspajająca...
Góra
Mężczyzna Offline
PostNapisane: 6 sie 2015, o 21:56 
Użytkownik

Posty: 394
Lokalizacja: Warszawa
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 09:51 
Gość Specjalny
Avatar użytkownika

Posty: 4974
Lokalizacja: Lozanna
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 2spojny wierzcholkowo  Matiks21  4
 graf - czy dobrze narysowałem ?  spec_u  0
 Dla podanego grafu narysuj graf liniowy  pioootrek  0
 Graf nieskierowany - zadanie 3  kasia00  1
 Pokaż że graf prosty...  magdalenka88  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl