Wpis z mikrobloga

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?
@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 zadział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ć?
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ć.
@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 i