Przecięcia w grafie

[mol_ksiazkowy]

Niech \(\displaystyle{ cr(G)}\) będzie minimalną możliwie liczbą przecięć krawędzi w przedstawieniu na płaszczyźnie grafu \(\displaystyle{ G}\); tj. gdy np. \(\displaystyle{ G}\) jest planarny to \(\displaystyle{ cr(G)=0}\), \(\displaystyle{ cr(K_{3,3})=1}\) itd.

Wyznaczyć \(\displaystyle{ cr(G)}\) dla tych grafów:
graf Petersena
kostka \(\displaystyle{ Q_4}\)
graf Heawooda
dwudzielnego \(\displaystyle{ K_{2,4}}\)
\(\displaystyle{ 2n }\) kąta foremnego; krawędziami są jego boki i przekątne główne
\(\displaystyle{ K_6 }\)

[arek1357]

Otóż w tym zadaniu nasunęła mi się jedna myśl ponieważ stopnie wierzchołków każdego z tych grafów są właściwie takie same, więc, żeby określić, ile wynosi: \(\displaystyle{ cr(G)}\) wykonuję sobie w zeszycie rysunki a ponieważ nie chce mi się tu rysować to może opowiem:

np.: dla grafu o stopniu wierzchołka trzy niech będzie to graf Petersena zaznacza sobie środek będący jednym punktem grafu i od tego środka rysuję sobie trzy półproste o początku w tym punkcie na każdej z tych półprostych zaznaczam po trzy wierzchołki grafu nie licząc tego środkowego...

łatwo sobie to rozrysować tak aby zobaczyć, że dla tego grafu żadna z krawędzi nie musi się przecinać z żadną a co za tym idzie \(\displaystyle{ cr(P)=0}\)

W kostce czterowymiarowej mamy: 16 wierzchołków, 32 krawędzie co łatwo sprawdzić, co daje nam, że z każdego wierzchołka wychodzi dokładnie cztery krawędzie, jak łatwo stwierdzić, jest to graf dwudzielny o dwóch składowych spójnych , rysując jedną składową w sposób opisany powyżej z tymże ze środka wychodzą cztery półproste o wspólnym początku i na trzech półprostych zaznaczam po cztery wierzchołki a na czwartej trzy, i bawiąc się w rysowanie można zauważyć, że \(\displaystyle{ cr(Q_{4})=1}\).

W grafie o 2n wierzchołkach z głównymi przekątnymi w sposób analogiczny jak w pierwszym przykładzie bo stopień każdego wierzchołka wynosi 3 ...
Liczba przecięć daje zero...

Dodano po 3 minutach 48 sekundach:
W grafie Heawooda bardzo specyficzny graf stopień każdego wierzchołka trzy a więc sposób analogiczny jak wyżej , wierzchołków jest czternaście ,
wychodzi mi trzy przecięcia....

Reasumując wydaje się to chyba najbardziej ludzki i organoleptyczny sposób sprawdzania planarności...

Dodano po 8 minutach 48 sekundach:
W grafie dwudzielnym natomiast \(\displaystyle{ K_{2,4}}\) zakładając, że jest to graf pełny otrzymuję chcąc nie chcąc...

\(\displaystyle{ cr(K_{2,4})=0}\)

Dodano po 9 minutach 56 sekundach:
Natomiast w \(\displaystyle{ cr(K_{6})=3}\) - jest to graf pełny...

Dodano po 13 godzinach 16 minutach 56 sekundach:
Przepraszam co do kostki czterowymiarowej ale to nie będzie graf dwurzędowy bo to by nie było jest to graf regularny , każdy wierzchołek rzędu 4...

Liczba cr chyba raczej dwa...

[kerajs]

np.: dla grafu o stopniu wierzchołka trzy niech będzie to graf Petersena zaznacza sobie środek będący jednym punktem grafu i od tego środka rysuję sobie trzy półproste o początku w tym punkcie na każdej z tych półprostych zaznaczam po trzy wierzchołki grafu nie licząc tego środkowego...

łatwo sobie to rozrysować tak aby zobaczyć, że dla tego grafu żadna z krawędzi nie musi się przecinać z żadną a co za tym idzie \(\displaystyle{ cr(P)=0}\)

A mógłbyś pokazać grafikę to obrazującą.

Z tego co mi wiadomo, to graf Petersena nie jest planarny, a mi (mimo kilku prób) nie udaje się zejść poniżej dwóch przecięć.

PS
Potwierdzam że graf dwudzielny 2,4 jest planarny, a dla kliki 6 rysunki sugerują 3 przecięcia.

[arek1357]

Ok pokażę jakiś rysunek

Dodano po 19 minutach 18 sekundach:
zapodaję dla Petersena:



Dodano po 4 minutach 53 sekundach:
Przepraszam za szpetotę rysunku, dla pozostałych jest podobnie...

Dodano po 6 minutach 56 sekundach:
Możliwe że to nie jest graf Petersena tylko dwurzędowy

Dodano po 3 minutach :
istotnie Peterson ma cr=2

[mol_ksiazkowy]

Jeszcze inny problem: Czy istnieje graf w którym \(\displaystyle{ cr(G)= 5}\) i dla którego po usunięcu jednej krawędzi będzie planarny ?

[mol_ksiazkowy]

Przepraszam co do kostki czterowymiarowej ale to nie będzie graf dwurzędowy bo to by nie było jest to graf regularny , każdy wierzchołek rzędu 4...

Liczba cr chyba raczej dwa...

może jakiś rysunek i/lub jego opis...