Kilka pytań o grafy

[Fixus]

Witam, poniżej co do których swoich odpowiuedzi nie jestem pewien. Bardzo proszę o sprawdzenie. Może być 0,1,2,3 poprawnych odpowiedzi

1) Graf pełny \(\displaystyle{ G = (V,E)}\) gdzie \(\displaystyle{ |V|=9}\) jest grafem
a) Eulera i Hamiltona
b) Eulera lub Hamiltona
c) Eulera, ale nie hamiltona

Wydaje mi się, że poprawna opodiwedź to "a" dlatego, że każdy wierzchołek ma parzysty stopień co daje nam graf eulera oraz dlatego, że każdy graf pełny jest grafem hamiltona. Czy mam rację ?

2) Każdy graf pełny jest grafem
a) planarny
b) acykliczny
c) regularny

Jest regularny bo każdy wierzchołek ma taki sam stopień. Pozostałe wydają mi się nieprawidłowe

3) Graf relacji zwrotnej i symetrycznej jest grafem
a) prostym i dwudzielnym
b) prostym i spójnym
c) planarnym i regularnym

Według mnie odpowiedź b jest poprawna. Nie wiem czy "c" też nie jest, ale jeszcze nie do końca rozumiem czym są grafy planarne więc ciężko mi zdecydować

Bardzo proszę o info czy dobrze zrobiłem i czy odpowiedź c jest poprawna w 3 pytaniu

[norwimaj]

1. Skoro zaznaczyłeś odpowiedź a), to zaznacz też b). Tak będzie logicznie.

2. Żeby rozwiać wątpliwości co do punktu a), czy potrafisz podać jakikolwiek (skończony) przykład grafu nieplanarnego?

3. Jeśli relacja jest zwrotna, to są "pętelki" przy wierzchołkach, więc graf nie jest prosty. Nie widać też powodu, dlaczego miałby być spójny. Co do punktu c) graf pełny z pętelkami jest przykładem relacji zwrotnej i przechodniej, czyli to podobnie jak 2a). Regularny też być nie musi.

[Fixus]

z nieplanarnym wiem, że graf \(\displaystyle{ K _{5}}\) nie jest planarny, ale wiem to bo tak wyczytałem co wcale nie znaczy, że rozumiem. Dziś mam zamiar skumać te planarne

Może wyjaśnie, dlaczego uważam, że w 3 b jest poprawna. Jeśli weźmiemy 2 punkty A i B które są ze sobą w relacji symetrycznej i same ze sobą w relacji zwrotnej to przecież mają ten sam stopień (2)
Dodatkowo są ze sobą połączone więc istnieje droga między nimi zarówno z A do B jak i z B do A dlatego uznałem, że jest to graf spójny

[yorgin]

Może wyjaśnie, dlaczego uważam, że w 3 b jest poprawna. Jeśli weźmiemy 2 punkty A i B które są ze sobą w relacji symetrycznej i same ze sobą w relacji zwrotnej to przecież mają ten sam stopień (2)
Dodatkowo są ze sobą połączone więc istnieje droga między nimi zarówno z A do B jak i z B do A dlatego uznałem, że jest to graf spójny

W grafie prostym nie występują krawędzie wielokrotne oraz pętle postaci \(\displaystyle{ v\to v}\).
Co ma stopień do tego?

I skąd pewność, że w ogóle jakiekolwiek różne wierzchołki muszą być połączone krawędzią?

[Fixus]

fakt, zapomniałem o tej własności proste. wsio jasne z tym

[norwimaj]

Grafy planarne, to takie, które dają się narysować na kartce tak, żeby żadne dwa wierzchołki nie były w tym samym punkcie i żeby żadne dwie krawędzie się nie przecinały (chyba że końcami). Podgraf grafu planarnego też jest planarny. Zatem \(\displaystyle{ K_5}\) po dorysowaniu pętelek też jest nieplanarny, więc 3c jest nieprawdziwe.

Jeśli weźmiemy 2 punkty A i B które są ze sobą w relacji symetrycznej i same ze sobą w relacji zwrotnej to przecież mają ten sam stopień (2)

Z tego, że dwa wierzchołki mają stopnie większe lub równe dwa, nie wynika że mają równe stopnie. I, jak już zostało zauważone, nie wszystkie pary wierzchołków muszą być w relacji.

[Fixus]

ok a możesz mi wyjaśnić jedno. bo generalnie rozumiałem grafy planarne dopóki nie zobaczyłem tego


a szczególnie stwierdzenia
Przykład 2. Planarność grafu nie pociąga za sobą tego, że każdy jego rysunek
płaski nie ma krawędzi, które się nie przecinają

To mnie wybiło

[norwimaj]

Pod tym stwierdzeniem masz rysunek, który to obrazuje. Graf \(\displaystyle{ K_4}\) można narysować nieplanarnie albo planarnie. Ponieważ da się go narysować planarnie, to jest planarny.

[Fixus]

i wszystko jasne. bardzo dziękuje