szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 27 mar 2017, o 23:25 
Użytkownik

Posty: 11
Lokalizacja: Kraków
wykaz ze jesli graf G=(V,E) dwudzielny jest d-regularny, to nie istnieje w nim most.

-- 27 mar 2017, o 22:29 --

moja idea dowodu jest taka ze zalozmy ze istnieje ten most. a wiec usunmy jedna krawedz laczaca dwa wierzcholki tak, aby powstaly dwie spojne skladowe. Jednak gdy usuniemy ta jedna krawedz pomiedzy tymi dwoma wierzcholkami to zostanie na pewno jeszcze jakas poniewaz d\ge 2 z zalozenia, a wiec nadal sa one polaczone , a wiec dochodzimy do sprzecznosci a wiec hipoteza jest sprzeczna a wiec teza prawdziwa wiec nie istnieje most w takim grafie. czy ktos cos ?
Góra
Mężczyzna Offline
PostNapisane: 28 mar 2017, o 10:40 
Użytkownik

Posty: 45
Weźmy graf G-{uv}, gdzie uv jest mostem i rozważmy jedną ze spójnych składowych H tego grafu taką, że u \in V(H) . H jest grafem dwudzielnym, wobec tego V(H) = (V(H) \cap X) \cup (V(H) \cap Y) (gdzie X i Y są klasami dwudzielności grafu G) musi zatem zachodzić zależność
d \cdot (\left| V(H) \cap X\right| - 1) + d-1 = d(\left| V(H) \cap Y\right|). Otrzymujemy

\frac{d-1}{d} = (\left| V(H) \cap Y\right|  - \left| V(H) \cap X\right| +1), a to jest sprzeczność, bo dla d \ge 2 liczba \frac{d-1}{d} jest niecałkowita.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 [GRAFY] Ile jest grafów  ematyk  0
 Narysowac 4 grafy (Hamiltonowskie Eulerowskie)  devonsix  2
 grafy(mampa)  macko88  0
 Grafy Planarne - zadanie 2  jabol460  2
 Dowód Grafy 2-spójne  adri  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl