Przecięcia prostych

[mol_ksiazkowy]

Na płaszczyźnie danych jest \(\displaystyle{ n}\) prostych \(\displaystyle{ (n > 2) }\). Żadne z nich nie są równoległe ani żadne trzy nie przecinają się w jednym punkcie. Każdemu punktowi przecięcia tych prostych przypisuje się dodatnią liczbę całkowitą mniejszą od \(\displaystyle{ n}\). Udowodnić, że można dokonać tego przypisania w taki sposób, by na każdej prostej pojawiły się, w punktach jej przecięcia z pozostałymi prostymi, wszystkie liczby od \(\displaystyle{ 1}\) do \(\displaystyle{ n−1}\), wtedy i tylko wtedy, gdy liczba \(\displaystyle{ n}\) jest parzysta.

[FasolkaBernoulliego]

Dla \(\displaystyle{ n=2^k}\) jest proste... jak należy ponumerować np. dla 6 prostych? Może ktoś się zna na kwadratach łacińskich?

[arek1357]

Ja się dobrze znam na łacinie (ale podwórkowej)...

A co do zadania wystarczy utożsamić proste z punktami . I teraz mówiąc, że każde dwie proste mają punkt wspólny, możemy powiedzieć :
"każde dwa punkty mają wspólną krawędź"...

I tak transponujemy proste na punkty a punkty(wspólne dwóch prostych) na krawędzie.

Powstaje graf prosty doskonały, czyli taki, gdzie każde dwa punkty lub wierzchołki jak kto woli są połączone...(krawędzią)

Więc nasze zadanie sprowadza się do kolorowania krawędzi grafu , ale tak aby z żadnego wierzchołka nie wychodziły krawędzie jednego koloru....

Co odpowiada liczbom: \(\displaystyle{ \left\{ 1,2,3,4,...,n-1\right\} }\)

Ale mamy słynne twierdzenie mówiące , że każdy pełny graf ma liczbę chromatyczną ( co odpowiada naszym kolorom , albo liczbom)

\(\displaystyle{ \chi(K_{n})=\begin{cases} n , n=2k+1\\ n-1 , n=2k\end{cases} }\)


Gdzie n to liczba wierzchołków (a co za tym idzie liczba prostych) naszego grafu pełnego...

a \(\displaystyle{ n}\) jest liczbą parzystą

Najlepiej widać to na przykładzie kwadratu z przekątnymi \(\displaystyle{ (n=4)}\) i trójkąta, \(\displaystyle{ (n=3)}\) potem już nie widać nic pajęczyna...

cnd...

[kerajs]

jak należy ponumerować np. dla 6 prostych?

Choćby tak (dla przejrzystości użyłem kolorów zamiast cyfr) :

Ukryta treść:    

6prostych.png (9.76 KiB) Przejrzano 954 razy

To może jeszcze dodam że dla n prostych jest \(\displaystyle{ \frac{(n-1)n}{2}}\) punktów przecięcia.
Jeśli układ da się ponumerować to każda liczba wystąpi taką samą ilość razy (na rysunku to 3)

Dla nieparzystych \(\displaystyle{ n}\) (niech \(\displaystyle{ n=2k+1}\)) ilość punktów przecięcia to \(\displaystyle{ k(2k+1) }\), a liczba ta nie jest podzielna przez \(\displaystyle{ 2k}\) (a tyle jest wtedy liczb od 1 do n-1), więc nie można tego zestawu ponumerować.

Dla parzystych \(\displaystyle{ n}\) (niech \(\displaystyle{ n=2k}\)) ilość punktów przecięcia to \(\displaystyle{ (2k-1)k }\), a liczba ta jest podzielna przez \(\displaystyle{ 2k-1}\) więc te zestawy potencjalnie mogą być ponumerowane. A że są, to udowodnił powyżej Arek.

Dodano po 39 minutach 1 sekundzie:
Choć przypuszczam że Arek chciał napisać, iż indeks chromatyczny grafu pełnego o parzystej liczbie wierzchołków (n) wynosi n-1.

[FasolkaBernoulliego]

No pewnie, ale ze mnie dzban.

To tylko wyjaśnię o co mi chodziło z tymi kwadratami. Taki graf można przedstawić w postaci macierzy n na n z pustą główną przekątną, niezmienniczą ze względu na transpozycję. Jeżeli umówimy się, że wstawiamy w przekątną 1, to pozostaje uzupełnić wszystkie pozostałe elementy macierzy tak, aby był spełniony warunek, że w każdym wierszu i każdej kolumnie ma być każda liczba od 1 do n, czyli zbudować kwadrat łaciński. Czy to twierdzenie podaje konstrukcję takiego kolorowania czy jest tylko egzystencjonalne, bo nie miałem za dużo styczności z teorią grafów?

[arek1357]

Choć przypuszczam że Arek chciał napisać, iż indeks chromatyczny grafu pełnego o parzystej liczbie wierzchołków (n) wynosi n-1

No właśnie tak napisałem i to miałem na myśli...

Dodano po 42 minutach 56 sekundach:
Najpierw do tego zadania chciałem użyć grafów dwudzielnych, ale to nic nie dało, a ładnie wszystko się zamyka w grafach pełnych...

[Slup]

No pewnie, ale ze mnie dzban.

To tylko wyjaśnię o co mi chodziło z tymi kwadratami. Taki graf można przedstawić w postaci macierzy n na n z pustą główną przekątną, niezmienniczą ze względu na transpozycję. Jeżeli umówimy się, że wstawiamy w przekątną 1, to pozostaje uzupełnić wszystkie pozostałe elementy macierzy tak, aby był spełniony warunek, że w każdym wierszu i każdej kolumnie ma być każda liczba od 1 do n, czyli zbudować kwadrat łaciński. Czy to twierdzenie podaje konstrukcję takiego kolorowania czy jest tylko egzystencjonalne, bo nie miałem za dużo styczności z teorią grafów?

Nie znam tego twierdzenia. Nie trzeba jednak z niego korzystać.

Niech \(\displaystyle{ n}\) będzie liczbą parzystą. Niech te proste to będą \(\displaystyle{ L_0,...,L_{n-1}}\). Wówczas punktowi przecięcia prostych \(\displaystyle{ L_i}\) oraz \(\displaystyle{ L_j}\) przypisujemy liczbę resztę \(\displaystyle{ i+j\,\mathrm{mod}\,n-1}\). Jest to liczba z przedziału \(\displaystyle{ \{1,...,n-1\}}\) i można łatwo sprawdzić, że takie numerowanie spełnia warunki zadania. Tłumacząc to na język grafów jest to żądane kolorowanie.

Myślę zresztą, że powyższe rozumowanie może służyć za część dowodu twierdzenia, które arek1357 przytoczył.

[FasolkaBernoulliego]

Nie do końca rozumiem. Biorę \(\displaystyle{ n=6}\) i wypełniam według wskazania:

x 1 2 3 4 0
1 x 3 4 0 1
2 3 x 0 1 2
3 4 0 x 2 3
4 0 1 2 x 4
0 1 2 3 4 x

Wtedy np. dla prostej \(\displaystyle{ L_1}\) w przecięciu z prostą \(\displaystyle{ L_0}\) i \(\displaystyle{ L_5}\) mam kolor nr 1.

[Slup]

Pomyliłem się. Powinno być modulo \(\displaystyle{ n}\). Poza tym to bardziej skomplikowane niż mi się wydawało kilka godzin temu. Zamieszczam pełne rozwiązanie.

Niech już będzie w terminach tego kolorowania grafów. Nie ma potrzeby udawać, że to zadanie na jakiś inny temat.

Weźmy graf pełny \(\displaystyle{ K_n}\). Numerujemy wierzchołki grafu \(\displaystyle{ K_n}\) liczbami \(\displaystyle{ 0,1,...,n-1}\). Przez \(\displaystyle{ (i,j)}\) oznaczamy krawędź, która łączy wierzchołek o numerze \(\displaystyle{ i}\) z wierzchołkiem o numerze \(\displaystyle{ j}\). Krawędź \(\displaystyle{ (i,j)}\) kolorujemy przy użyciu barwy o numerze:
$$i+j\,\mathrm{mod}\,n$$
Oczywiście ta barwa to jest jakiś element ze zbioru \(\displaystyle{ \{0,1,...,n-1\}}\). Można łatwo sprawdzić, że jest to kolorowanie grafu \(\displaystyle{ K_n}\) przy użyciu \(\displaystyle{ n}\) kolorów.

dowód:    

Trzeba sprawdzić, że dla ustalonego wierzchołka o numerze \(\displaystyle{ i\in \{0,1,...,n-1\}}\) różne krawędzie, które wychodzą z tego wierzchołka, są pokolorowane różnymi kolorami. Załóżmy, że krawędzie \(\displaystyle{ (i,j_1)}\) oraz \(\displaystyle{ (i,j_2)}\) są pokolorowane tym samym kolorem. Wówczas
$$i+j_1 \equiv i+j_2\,\mathrm{mod}\,n$$
co oznacza, że \(\displaystyle{ j_1 \equiv j_2\,\mathrm{mod}\,n}\), więc \(\displaystyle{ j_1 = j_2}\) czyli \(\displaystyle{ (i,j_1)=(i,j_2)}\).

Dodatkowo z zasady szufladkowej widać, że to kolorowanie musi pomijać jeden kolor przy każdym wierzchołku, bo z każdego wierzchołka wychodzi \(\displaystyle{ n-1}\) krawędzi. Jeśli \(\displaystyle{ i}\) to ustalony wierzchołek, to mamy następujące kolory krawędzi, które z niego wychodzą:
$$i+0\,\mathrm{mod}\,n,\,i+1\,\mathrm{mod}\,n,\,...,\,i+(i-1)\,\mathrm{mod}\,n,i+(i+1)\,\mathrm{mod}\,n,...,i+(n-1)\,\mathrm{mod}\,n$$
co sugeruje, że żadna krawędź przy tym wierzchołku nie ma koloru \(\displaystyle{ c_i = 2 i\,\mathrm{mod}\,n}\). Łatwo sprawdzić, że tak faktycznie jest.

Załóżmy teraz na chwilę, że \(\displaystyle{ n}\) jest liczbą nieparzystą. Wówczas
\(\displaystyle{ c_i \not \equiv c_j\,\mathrm{mod}\,n}\)
dla różnych wierzchołków \(\displaystyle{ i,j}\).

Otrzymujemy następujący.

Wniosek.
Dla dowolnego \(\displaystyle{ n}\) istnieje kolorowanie krawędzi grafu \(\displaystyle{ K_n}\) przy użyciu \(\displaystyle{ n}\) różnych kolorów. Ponadto jeśli \(\displaystyle{ c_i}\) nie jest kolorem żadnej krawędzi przy wierzchołku \(\displaystyle{ i}\), to przy założeniu, że \(\displaystyle{ n}\) jest nieparzysta otrzymujemy, że
\(\displaystyle{ c_i\neq c_j}\)
dla różnych \(\displaystyle{ i,j}\).

No dobra. To teraz załóżmy, że liczba \(\displaystyle{ n+1}\) jest parzysta. Wtedy graf \(\displaystyle{ K_{n+1}}\) to graf \(\displaystyle{ K_n}\) plus jeden dodatkowy wierzchołek \(\displaystyle{ p}\) i krawędzie, które łączą \(\displaystyle{ p}\) z każdym wierzchołkiem grafu \(\displaystyle{ K_n}\). Z Wniosku wiadomo, że można wierzchołki grafu \(\displaystyle{ K_n}\) pokolorować przy użyciu \(\displaystyle{ n}\) kolorów. Dodatkowo dla każdego wierzchołka \(\displaystyle{ i}\) grafu \(\displaystyle{ K_n}\) istnieje kolor \(\displaystyle{ c_i}\), który nie jest kolorem żadnej krawędzi w \(\displaystyle{ K_n}\) wychodzącej z \(\displaystyle{ i}\). Kolorujemy krawędź \(\displaystyle{ (p,i)}\) w grafie \(\displaystyle{ K_{n+1}}\) kolorem \(\displaystyle{ c_i}\). Z Wniosku i faktu, że \(\displaystyle{ n}\) jest nieparzysta dostajemy, że to jest poprawne kolorowanie grafu \(\displaystyle{ K_{n+1}}\) przy użyciu \(\displaystyle{ n}\) kolorów.

[FasolkaBernoulliego]

Super, dzięki!