szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 27 mar 2017, o 22: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 09: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 samodopełniające się  driller12  1
 Wszystkie grafy nieplanarne o 6 wierzchołkach  donmaciej  2
 Grafy  Boran  0
 Grafy proste izomorficzne ze swoim dopełnieniem.  Miszel1234  4
 Grafy regularne, istnienie  xiikzodz  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl