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