Udowodnij, że krawędzie dowolnego grafu nieskierowanego
: 15 lip 2014, o 00:36
Witam,
Udowodnij, że krawędzie dowolnego grafu nieskierowanego można skierować w taki sposób, że dla każdego wierzchołka \(\displaystyle{ v}\) spełniony będzie warunek:
\(\displaystyle{ |\deg_{in}(v) -\deg_{out}(v)}|\le 1}\)
Może ktoś podać wskazówkę ? Pod spojlerem może być nawet "mocniejsza" wskazówka.
Udowodnij, że krawędzie dowolnego grafu nieskierowanego można skierować w taki sposób, że dla każdego wierzchołka \(\displaystyle{ v}\) spełniony będzie warunek:
\(\displaystyle{ |\deg_{in}(v) -\deg_{out}(v)}|\le 1}\)
Może ktoś podać wskazówkę ? Pod spojlerem może być nawet "mocniejsza" wskazówka.