Matematyka.pl

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...

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.}\)

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}\)

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:.

Bardzo dziękuję za pomoc!