Graf na okręgu

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Awatar użytkownika
Legisl
Użytkownik
Użytkownik
Posty: 37
Rejestracja: 6 cze 2019, o 15:41
Płeć: Mężczyzna
Lokalizacja: Gdańsk
Podziękował: 15 razy
Pomógł: 1 raz

Graf na okręgu

Post autor: Legisl »

Niech będzie dany \(\displaystyle{ n}\)-wierzchołkowy graf spójny \(\displaystyle{ G}\), którego wierzchołki leżą na okręgu i nie istnieją \(\displaystyle{ 2}\) takie wierzchołki o tej samej współrzędnej. Krawędzie tego grafu są prostymi. Pytanie: Na ile pól krawędzie grafu \(\displaystyle{ G}\) dzielą wnętrze okręgu? Np. jeśli weźmiemy graf \(\displaystyle{ G}\) o 2 wierzchołkach to jak poprowadzimy prostą łączącą te \(\displaystyle{ 2}\) wierzchołki (krawędź), to okrąg zostanie podzielony na \(\displaystyle{ 2}\) części. Analogicznie dla \(\displaystyle{ n=3}\) mamy \(\displaystyle{ 4}\) części, itd...
Ostatnio zmieniony 26 lip 2019, o 17:28 przez Afish, łącznie zmieniany 3 razy.
Powód: Poprawa wiadomości.
SloppyTurtle
Użytkownik
Użytkownik
Posty: 8
Rejestracja: 2 paź 2017, o 17:44
Płeć: Mężczyzna
Lokalizacja: Polska
Pomógł: 1 raz

Re: Graf na okręgu

Post autor: SloppyTurtle »

Jak wyglądają krawędzie tego grafu? To ma być klika? Np. jeżeli jest to cykl prosty, to odpowiedź to \(\displaystyle{ n+1}\) dla \(\displaystyle{ n \ge 3.}\)
Ostatnio zmieniony 26 lip 2019, o 20:28 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Całe wyrażenia matematyczne umieszczaj w tagach [latex] [/latex].
Awatar użytkownika
Legisl
Użytkownik
Użytkownik
Posty: 37
Rejestracja: 6 cze 2019, o 15:41
Płeć: Mężczyzna
Lokalizacja: Gdańsk
Podziękował: 15 razy
Pomógł: 1 raz

Re: Graf na okręgu

Post autor: Legisl »

Tak jak napisałem:
Krawędzie tego grafu są prostymi.
Okrąg i proste są opisane na płaszczyźnie \(\displaystyle{ \RR^{2}}\) z metryką euklidesową. Podam kilka wartości dla początkowych \(\displaystyle{ n}\) , zaczynając od \(\displaystyle{ n=1}\) :
1. \(\displaystyle{ 1}\)
2. \(\displaystyle{ 2}\)
3. \(\displaystyle{ 4}\)
4. \(\displaystyle{ 8}\)
5. \(\displaystyle{ 16}\)
6. \(\displaystyle{ 31}\)
7. \(\displaystyle{ 57}\)
8. \(\displaystyle{ 99}\)
Bourder
Użytkownik
Użytkownik
Posty: 73
Rejestracja: 19 mar 2016, o 12:38
Płeć: Mężczyzna
Podziękował: 15 razy
Pomógł: 10 razy

Re: Graf na okręgu

Post autor: Bourder »

Jeżeli to jest klika, to obszary możemy podzielić na dwa typy: wewnątrz grafu i na jego zewnątrz. Obszarów na zewnątrz dla \(\displaystyle{ n \ge 3}\) jest \(\displaystyle{ n}\). Obszarów wewnątrz jest najwyżej tyle, ile obszarów wewnątrz wielokąta wypukłego, którego żadne \(\displaystyle{ 3}\) przekątne nie mają punktu wspólnego (można przyjąć wielokąt foremny). Rozwiązanie tego problemu jest tutaj: https://math.stackexchange.com/questions/241887/what-is-the-maximum-number-of-regions-produced-i-e-fn-by-joining-all-vert.

Ostatecznie, dla \(\displaystyle{ n \ge 4}\) mamy wzór:
Ukryta treść:    
.
Awatar użytkownika
Legisl
Użytkownik
Użytkownik
Posty: 37
Rejestracja: 6 cze 2019, o 15:41
Płeć: Mężczyzna
Lokalizacja: Gdańsk
Podziękował: 15 razy
Pomógł: 1 raz

Re: Graf na okręgu

Post autor: Legisl »

Bardzo dziękuję za pomoc!
ODPOWIEDZ