Z Wikipedii, wolnej encyklopedii
Twierdzenie o liczbie krawędzi pozwala stwierdzić, czy graf jest hamiltonowski.
Jeśli graf prosty o
wierzchołkach ma co najmniej
![{\displaystyle {\frac {1}{2}}\cdot (n-1)(n-2)+2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/69afbb41dedece42b973ed5c55c5fd47f051a8d6)
krawędzi, to jest hamiltonowski.
Dla dowolnego grafu prostego
załóżmy, że zachodzi
![{\displaystyle |E(G)|\geqslant {\frac {1}{2}}\cdot (n-1)(n-2)+2={n-1 \choose 2}+2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fa1df158f07639a00397e303e25c9d3e2d2fa7ef)
i weźmy wierzchołki
i
takie, że:
![{\displaystyle \{v,u\}\notin E(G).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cf0224ad2824163d60ff1db79ed3ef2333bd7271)
Niech
będzie grafem
z którego usunięto wierzchołki
i
oraz kończące się w nich krawędzie. Ponieważ:
![{\displaystyle \{v,u\}\notin E(G),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5ca5ee64d30b5e42e28a1fec304abf0705c7b75f)
więc usunęliśmy
krawędzi i dwa wierzchołki.
jest podgrafem grafu
a więc:
![{\displaystyle {n-2 \choose 2}=|E(K_{n-2})|\geqslant |E(H)|\geqslant {n-1 \choose 2}+2-\deg(v)-\deg(u),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/519e587f16b8a89f1c7cba6785ac6ba99638f82a)
z czego wynika, że:
![{\displaystyle \deg(v)+\deg(u)\geqslant {n-1 \choose 2}-{n-2 \choose 2}+2={\frac {1}{2}}(n-2)\cdot 2+2=n,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6e1cba6f0db88193d22767a7501838c05029eabb)
a więc
spełnia założenia twierdzenia Orego.
Najważniejsze pojęcia |
|
---|
Wybrane klasy grafów |
|
---|
Algorytmy grafowe |
|
---|
problemy grafowe |
|
---|
Inne zagadnienia |
|
---|