201305291643

201305291643



| Jeśli G jest grafem dwudzielny, to każdy cykl w G ma długość parzystą.

•    Zbiorem rozspajającym grafu spójnego G nazywamy zbiór krawędzi, których usunięcie spowoduje, że graf G przestanie być spójny.

•    Rozcięcie jest to zbiór rozspajający, którego żaden pozdbiór właściwy nie jest już zbiorę rozspajającym.

•    Jeśli rozcięcie składa się z jednej krawędzi e, to tę krawędź nazyway mostem.

i Jeśli graf G jest spójny, to jego spójnością krawędziową A(G) nazyway liczbę-krawędzi należących do najmniej-licznego rozcięcia grafu G.

•    Zbiorem rozdzielający grafu spójnego G nazyway zbiór wierzchołków których usunięcie powoduje, że ten graf przestaje być spójny.

•    Graf spójny G nazywamy grafem eulerowskim, jeśli istnieje w nim cykl Eulera.

•    Graf spójny G który nie jest grafem Eulera, nazwiemy grafem pół-eulerowskim, jeśli zawiera drogę Eulera.

Twierdzenie Eulera, 1736 Graf spójny G jest grafem eulerowskim wtedy i tylko wtedy, gdy stopień

każdego wierzchołka grafu G jest liczbą parzystą.

Twierdzenie Graf spójny jest grafem półeulerowski wtedy i tylko wtedy, gdy a dokładnie dwa wierzchołki stopnia nieparzystego.

I Graf spójny mający cykl Hamiltona nazywamy Hamiltonowskim.

• Graf spójny który nie jest hamiltonowski nazywamy pólhamiltonowski jeśli zawiera ścieżkę Hamiltona.

Twierdzenie Orego, 1960 Jeśli graf prosty G ma n wierzchołków (gdzie n > 3) oraz

deg(v) + deg(w) > n

dla każdej pary wierzchołków niesąsiednich v i w, to graf G jest hamiltonowski.

Twierdzenie Diraca, 1952 Jeśli w grafie prostym G, który a n wierzchołków (gdzie n > 3), deg(v) > n/2 dal każdego wierzchołka v, to graf G jest hamiltonowski.

1


Wyszukiwarka

Podobne podstrony:
•    Jeśli G jest grafem bez pętli, to mówimy, że G jest grafem k- kolor owalnym,&nbs
Jeśli d jest średnicą śruby, to: E = 2d    HI = 0,7d R = 0,4d    H2 =
img072 Jeśli d jest średnicą śruby, to: E = 2d HI = 0,7d R = 0,4d u; K> II O 00 R1 = l,5d G =
□    Jeśli chodzi o osoby prawne, to też nie ma regulacji, ale wybrane kategorie
Polski KongresDrogowy iPolish Road Congres sl-Jeśli jest tak dobrze, to...?ZARZĄD DRÓG WOJEWÓDZKICH
P3084497 Od składu lawy zależy jaki powstanie wulkan. Jeśli jest bogata w krzemionkę to po zastygnię
Twierdzenie 3 Jeśli (R, 0, O) jest pierścieniem z jednością to (/?",©) jest grupą. Pierścień
Wniosek 1 Jeśli K jest ciałem skończonym to każda funkcja K —* K może być zapisana jako
image22 Miałem prosty układ z rodzicami - jeśli jest dobrze w szkole, to jeżdżę więcej. Było dobrze,
Tw. Bolzano-Cauchy ego Jeśli f:[a,b] jest ciągła oraz f(a)*f(b)<0 to istnieje c e (a,b) taM że
•    Jeśli jest równoznaczne z wypowiedzeniem to odwołuje się ze stanowiska,

więcej podobnych podstron