Graf na okręgu
- Legisl
- 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
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.
Powód: Poprawa wiadomości.
-
- 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
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] .
Powód: Całe wyrażenia matematyczne umieszczaj w tagach
- Legisl
- 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
Tak jak napisałem:
1. \(\displaystyle{ 1}\)
2. \(\displaystyle{ 2}\)
3. \(\displaystyle{ 4}\)
4. \(\displaystyle{ 8}\)
5. \(\displaystyle{ 16}\)
6. \(\displaystyle{ 31}\)
7. \(\displaystyle{ 57}\)
8. \(\displaystyle{ 99}\)
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}\) :Krawędzie tego grafu są prostymi.
1. \(\displaystyle{ 1}\)
2. \(\displaystyle{ 2}\)
3. \(\displaystyle{ 4}\)
4. \(\displaystyle{ 8}\)
5. \(\displaystyle{ 16}\)
6. \(\displaystyle{ 31}\)
7. \(\displaystyle{ 57}\)
8. \(\displaystyle{ 99}\)
-
- 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
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:
Ostatecznie, dla \(\displaystyle{ n \ge 4}\) mamy wzór:.
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ść: