[Zgredzimierz]

#matematyka #grafy

Jakiś Mireczek ogarnia grafy ?

[scotieb]

@Zgredzimierz Spytaj nauczyciela z gimnazjum XD

[koostosh]

@Zgredzimierz: tak

[Zgredzimierz]

@koostosh :D

[Blomex]

ale o co chodzi, bo z tego zapisu nie idzie nic wywnioskować?
m<= 3n-6 to warunek na istnienie grafu planarnego, jak rozumiem ma mieć 7 wierchołków? a to pierwsze to masz narysować 3 grafy regularne, kolejno o stopniach wierzchołków 1,2,4 i mające 10 wierzchołków?

[Blomex]

@Zgredzimierz: masz te grafy narysować czy co zrobić?

[Zgredzimierz]

@Blomex Tak narysować regularny graf n=10 1,2 i 3 stopnia

[Blomex]

@Zgredzimierz: no to sobie rysujesz, graf regularny nie musi być spójny, więc żeby wszystkie były stopnia 1 to po prostu rysujesz krawędź między wierzchołkami z których jeszcze nie wychodzi żadna krawędź. (spoiler na wikipedii: https://pl.wikipedia.org/wiki/Graf_regularny ). A graf o wszystkich wierzchołkach stopnia 2 to np jeden cykl. ze stopniem 4 trzeba chwilę pomyśleć ale powinno wyjść rysując "na pałę" (zauważ, że ten sam trick co przy zwiększaniu stopnia o 1

[w.....a]

Jak chcesz jak największą liczbę krawędzi to rób sobie trójkąty w nim.

@Blomex:
hmmmmm
Twierdzenie: jeśli w grafie planarnym G każdy zamknięty obszar (włącznie z "zewnętrzem") jest "trójkątem" to każdy graf planarny o tej samej ilości wierzchołków ma co najwyżej tyle samo krawędzi.
Twierdzenie intuicyjne, ale nie widziałem go nigdzie. Da się to jakoś szybko uzasadnić?

[w.....a]

Da się to jakoś szybko uzasadnić?

@wamaga:
@Blomex:
Sam sobie odpowiem: wzór Eulera wiąże ilość wierzchołków, krawędzi i ścian, zaś jeśli wszystkie ściany są trójkątami to da się wyliczyć ich ilość z krawędzi (2/3 k), więc mamy zależność ilości krawędzi od wierzchołków. Więc każdy z trójkątami ma tyle samo krawędzi. Oczywiście jeśli nie miałby samych trójkątów to nie byłby najlepszy ob można zawsze jakąś dorysować.

[w.....a]

@Zgredzimierz:
Tylko rysując zgodnie z radą tak aby wszystkie ściany były trójkątami - pamiętaj że zewnętrze też jest ścianą ( ͡° ͜ʖ ͡°)

[Blomex]

@wamaga: można też indukcyjnie: zaczynamy od trójkąta i w każdym kroku robimy:
(Algorytm:)
1. Wybieramy dowolny trójkąt z istniejących
2. Rysujemy wierzcholek w jego srodku i 3 krawędzie
3. Powstają 3 trójkąty zamiast 1, liczba wierzchołków zwiększa się o 1, ścian o 2, krawędzi o 3 więc wzóe eulera działa. Tak utworzony graf nadal jest planarny.
Z założenia indukcyjnego m=3n-6 (dziala dla trójkąta 3=3) po zwiększeniu liczby wierzchołków o 1