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

Posty: 10
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 ?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
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 
 Ile wierzchołków i krawędzi mają grafy, suma względem k i n  bartkam  0
 Grafy Cx a Kx  Tybias  4
 grafy, drzewa  gosienkaq  1
 drzewa spinające, grafy, rekurencja  mwmkh  1
 Grafy - Kod Prufera  rozpruwacz  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl