[Kombinatoryka] Kolorowanie punktów kratowych

[Swistak]

Jestem na 18-tce u Wąsa, więc to świetna okazja, aby zarzucić wam jakimś zadankiem!
Mamy sobie zaznaczone jakieś punkty kratowe w układzie współrzędnych (takie o obu współrzędnych całkowitych). Rozstrzygnij dla jakich układów tych punktów da się każdy pokolorować na czerwono albo zielono tak, aby różnica między punktami czerwonymi, a zielonymi w każdej kolumnie i w każdym wierszu nie była większa niż 1 (chodzi o różnice między liczbą zielonych i czerwonych punktów w ustalonej kolumnie, np. jak jest w niej zaznaczonych 11 punktów, to musi być 5 czerwonych i 6 zielonych albo na odwrót).

[smigol]

Czyli impreza przednia.

[Dumel]

popraw Wojtuś treść, bo sensu mało ma.

[Swistak]

smigol: Gdybym nie był świadom, że bawię się przednio, to bym o tym nie wspominał ;p. Ale to nie o tym temat.
Dumel: No zapomniało mi się "czerwonymi, a zielonymi", ale to chyba można się było domyślić ;p. Ewentualnie ostatnia część też mogła być trochę niejasna ;p.

[XMaS11]

Podam trochę przeformułowane rozwiązanie. Mianowicie udowodnię, że w każdym grafie bez pętli można tak pomalować krawędzie na biało i czarno, że dla każdego wierzchołka wartość bezwzględna różnicy pomiędzy liczbą wychodzących z niego czarnych krawędzi a liczbą wychodzących z niego białych krawędzi nie przekracza 1.
W tym celu połączmy wierzchołki o stopniu nieparzystym w pary i połączmy wierzchołki w każdej parze krawędzią (mogą pojawić się krawędzie wielokrotne). W otrzymanym grafie każdy wierzchołek ma parzysty stopień, zatem istnieje w nim cykl Eulera. Bierzemy sobie ten cykl i idziemy malując krawędzie na przemian na czarno i biało. Łatwo widać, że to pokolorowanie daje 'dobre' pokolorowanie wyjściowego grafu.

[Swistak]

No to to nie działa, bo nie mamy gwarancji, że wszystko się zgodzi dla wierzchołka, z którego startujemy, bo jak jest nieparzysta liczba krawędzi, to pierwsza i ostatnia będą takiego samego koloru i w tym wierzchołku różnica będzie wynosić 2.

[Dumel]

ta różnica może nawet wynieść 3.
aby naprawić rozwiązanie wystarczy dodać superwierzcholek i wystartować z niego.

[XMaS11]

Istotnie, wybaczcie ; (

[Swistak]

Racja, różnica może sięgnąć nawet 3.
Mógłbyś dokładniej opisać to rozwiązanie z superwierzchołkiem? Bo jeżeli mówisz o tym, co ja w tej chwili myślę, to to jest źle, ale może po prostu źle zrozumiałem, to co chciałeś powiedzieć.

[Dumel]

nieprecyzyjnie sie wyraziłem a i tak dalej byłaby luka, ale to już jest raczej ok:
do naszego zbioru punktów na płaszczyźnie dodajemy jeden extra, niech ma jakieś współrzędne \(\displaystyle{ (a,b)}\) gdzie na prostej \(\displaystyle{ y=a}\) już coś było a na \(\displaystyle{ x=b}\) jeszcze nic. konstruujemy ten graf Eulerowski i startujemy z wierzchołka symbolizującego kolumnę \(\displaystyle{ y=b}\)

[Swistak]

A w ogóle na czym polega zależność między punktami kratowymi, a jakimiś grafami, bo jeszcze nikt nic o tym nie powiedział?

-- 11 marca 2011, 19:46 --

Bump.
Dla mnie zadanie ciągle ma status nierozwiązanego, choć padły jakieś dobre pomysły (ale brakuje więcej niż jakiegoś 1 zdania).-- 11 marca 2011, 19:46 --Madafaka, nie bumpnęło się :<

[Swistak]

Bump, bump, bump!

[marcin_smu]

Każdy punkt odpowiada krawędzi naszego grafu, łączącej dany wiersz z daną kolumną. Dopóki w naszym grafie istnieją wierzchołki nieparzystego stopnia, bierzemy dowolną ścieżkę łączącą dwa takie wierzchołki (istnieje taka, ponieważ w każdej spójnej składowej jest parzysta ilość wierzchołków o nieparzystym stopniu), kolorujemy na przemian i wyrzucamy z grafu. Pozostanie nam graf, w którym każda spójna składowa jest cyklem Eulera. Graf jest dwudzielny, więc każdy z tych cykli ma parzystą długość, w nich też kolorujemy na przemian. Łatwo widać, że takie kolorowanie spełnia to warunki zadania.

[Swistak]

Idealnie .

[Mruczek]

Podam trochę przeformułowane rozwiązanie. Mianowicie udowodnię, że w każdym grafie bez pętli można tak pomalować krawędzie na biało i czarno, że dla każdego wierzchołka wartość bezwzględna różnicy pomiędzy liczbą wychodzących z niego czarnych krawędzi a liczbą wychodzących z niego białych krawędzi nie przekracza 1.
W tym celu połączmy wierzchołki o stopniu nieparzystym w pary i połączmy wierzchołki w każdej parze krawędzią (mogą pojawić się krawędzie wielokrotne). W otrzymanym grafie każdy wierzchołek ma parzysty stopień, zatem istnieje w nim cykl Eulera. Bierzemy sobie ten cykl i idziemy malując krawędzie na przemian na czarno i biało. Łatwo widać, że to pokolorowanie daje 'dobre' pokolorowanie wyjściowego grafu.

To rozwiązanie istotnie jest niedokończone, ale moim zdaniem można je łatwo poprawić i to bez żadnych superwierzchołków.

Ukryta treść:    

Zaczynamy jak u marcin_smu, tzn konstruujemy graf dwudzielny ze współrzędnych x i y, krawędzie to punkty.
Jeżeli wszystkie wierzchołki mają parzysty stopień to graf ma cykl Eulera. Ponadto ponieważ ten graf jest dwudzielny to cykl musi mieć parzystą długość, więc można pokolorować jego krawędzie na przemian dwoma kolorami.
W przeciwnym przypadku, tak jak u XMaS11 łączymy wierzchołki o stopniu nieparzystym w pary i te pary łączymy krawędziami. Być może w nowym grafie będą krawędzie wielokrotne, ale nie ma w nim pętli. Każdy wierzchołek ma parzysty stopień, więc dostajemy cykl Eulera. Zauważmy, że po usunięciu dodanych krawędzi z tego cyklu rozpadnie się on na krawędziowo rozłączne ścieżki. Teraz, nie tak jak poprzednio cały cykl z dodanymi krawędziami, ale tylko ścieżki pochodzące z początkowego grafu, będziemy kolorowali każdą osobno.
Tak więc kolorujemy krawędzie każdej ze ścieżek dwoma kolorami na przemian. Być może wierzchołki na takiej ścieżce się powtarzają, ale każde dwa kolejne wierzchołki to inny wierzchołek, bo w grafie nie ma pętli. Wierzchołek znajdujący się wewnątrz takiej ścieżki dostaje dwie krawędzie, przez które ta ścieżka przechodzi, o różnych kolorach.
Każda ze ścieżek zaczyna i kończy się wierzchołkiem, który na początku miał stopień nieparzysty. Taki wierzchołek nieparzysty może wystąpić na końcu którejś ze ścieżek dokładnie raz, ponieważ tylko jedna z dodanych krawędzi była z nim połączona. Tak więc krawędzie na końcach ścieżek nie mają znaczenia bo powiększają o jeden liczbę krawędzi pewnego koloru wierzchołków nieparzystych.
Ostatecznie różnica między liczbą krawędzi różnego koloru w każdym wierzchołku wynosi 0 dla wierzchołków parzystych i 1 dla nieparzystych.
To rozwiązanie w przeciwieństwie do podanego poprzednio, z usuwaniem ścieżek, łatwo przekłada się na algorytm liniowy zależny od liczby punktów.

Mam nadzieję, że jest ok.