Czy graf jest planarny ?

[marcin098]

Witam serdecznie wszystkich użytkowników forum? Nurtuje mnie kwestia jak sprawdzić czy następujący graf , jest planarny?

[leg14]

każdy graf planarny możesz pokolorować na 4 kolory - tego nie możesz

[Mruczek]

Nieprawda, ja znalazłem pokolorowanie tego grafu na \(\displaystyle{ 4}\) kolory - numerowanie zaczynam od wierzchołka pod literą "a" słowa "planarny" zamieszczonego obrazka, kolejność zgodnie z ruchem wskazówek zegara: \(\displaystyle{ 4, 1, 3, 2, 1, 4, 2, 3}\). Tak więc z twierdzenia o czterech barwach planarność tutaj nie zostanie rozstrzygnięta.

[leg14]

Ok, nie sprawdzałem Mruczek Twojego kolorowania, ale w takim razie mam dla OP'a taką propozycję:

Ze wzoru Eulera (wiążącego liczbę ścian, wierzchołków i krawędzi grafu planarnego) dostajesz standardowe oszacowanie \(\displaystyle{ m \le 3n -6}\), gdzie \(\displaystyle{ m}\) to liczba krawędzi, a \(\displaystyle{ n}\) liczba wierzchołków.
Zauważ, że Twój graf osiąga równość w tym oszacowaniu. Pomysł jest taki, by spróbować je wzmocnić w przypadku tego konkretnego grafu. Oryginalne oszacowanie otrzymujesz przy założeniu, że każdą ze ścian tworzą co najmniej \(\displaystyle{ 3}\) krawędzie. W ten sposób otrzymujesz nierówność \(\displaystyle{ 3f \le 2m}\), gdzie \(\displaystyle{ f}\) to liczba ścian. Ale w Twoim grafie masz co najmniej \(\displaystyle{ 3}\) (chyba znacznie więcej - policz) ścian które będą tworzone przez \(\displaystyle{ 4}\) krawędzie !

Ukryta treść:    

gdyby każda ściana grafu była tworzona przez co najmniej \(\displaystyle{ 4}\) krawędzie to miałbyś oszacowanie \(\displaystyle{ 4f \le 2m}\)

[Mruczek]

leg14, to co napisałeś powyżej niestety nie działa. Rysunek, na który patrzysz nie jest w postaci planarnej, więc nie możesz wypowiadać się o tym z ilu krawędzi składają się jego ściany - narysowany inaczej może mieć ściany innego kształtu. W ten sposób nie można wzmacniać tego oszacowania.

Wykorzystałem pakiet SageMath, okazuje się, że ten graf jednak jest planarny.
Oto jak go narysować:
Numerujemy wierzchołki liczbami od \(\displaystyle{ 0}\) do \(\displaystyle{ 7}\), zero dajemy poniżej "planarny" i w kolejności zgodnej ze wskazówkami zegara coraz większe.
Rysujemy graf w kolejności:
- najpierw cykl złożony z wierzchołków kolejno: 0, 1, 5, 6, 4, 7, 3
- łączymy 4 z 5 i 3 z 4
- dorysowujemy wierzchołek 2 wewnątrz cyklu 1, 0, 3, 4, 5
- łączymy 2 krawędziami z 1, 0, 3, 7, 4, 5 i dorysowujemy pozostałe krawędzie na zewnątrz grafu.

W tak narysowanym grafie każda ściana jest trójkątem (co leg14 napisał już na górze, żeby zachodziło powyższe oszacowanie każda ściana w grafie planarnym musi być trójkątem - można było wyjść od tego i próbować ręcznie narysować ten graf w taki sposób).

Generalnie pytania na forum o to czy graf narysowany na rysunku jest planarny są trochę bez sensu, bo jest wiele programów które potrafią to stwierdzić i nawet go narysować.