szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 14 cze 2018, o 22:58 
Użytkownik

Posty: 1
Lokalizacja: Tarnów
Witam serdecznie wszystkich użytkowników forum? Nurtuje mnie kwestia jak sprawdzić czy następujący graf https://zapodaj.net/3ce629d29a1fe.png.html , jest planarny?
Góra
Mężczyzna Offline
PostNapisane: 16 cze 2018, o 11:00 
Użytkownik
Avatar użytkownika

Posty: 2866
Lokalizacja: Radom
każdy graf planarny możesz pokolorować na 4 kolory - tego nie możesz
Góra
Mężczyzna Offline
PostNapisane: 20 cze 2018, o 04:11 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
Nieprawda, ja znalazłem pokolorowanie tego grafu na 4 kolory - numerowanie zaczynam od wierzchołka pod literą "a" słowa "planarny" zamieszczonego obrazka, kolejność zgodnie z ruchem wskazówek zegara: 4, 1, 3, 2, 1, 4, 2, 3. Tak więc z twierdzenia o czterech barwach planarność tutaj nie zostanie rozstrzygnięta.
Góra
Mężczyzna Offline
PostNapisane: 20 cze 2018, o 07:55 
Użytkownik
Avatar użytkownika

Posty: 2866
Lokalizacja: Radom
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 m \le 3n -6, gdzie m to liczba krawędzi, a 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 3 krawędzie. W ten sposób otrzymujesz nierówność 3f \le 2m, gdzie f to liczba ścian. Ale w Twoim grafie masz co najmniej 3 (chyba znacznie więcej - policz) ścian które będą tworzone przez 4 krawędzie !
Ukryta treść:    
Góra
Mężczyzna Offline
PostNapisane: 20 cze 2018, o 16:48 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
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 0 do 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ć.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ile jest dzielnikow liczby  Anonymous  6
 ile jest liczb 2cyfr/3cyfr, 5cyfr o pocz 12, bez cyfr 4 i 5?  Anonymous  1
 permutacje/ile jest sposobow ustawien/ -prosba o sprawdzenie  alamakota  3
 ile jest liczb trzycyfrowych, mniejszych od 555  Anonymous  1
 Dany jest zbiór A={a,b,c,d}  Nanu  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl