Graf prosty (nieskierowany, bez pętli i krawędzi wielokrotnych) nazwiemy \(\displaystyle{ d}\)-regularnym, jeśli każdy jego wierzchołek ma stopień równy \(\displaystyle{ d}\), czyli z każdego wierzchołka "wychodzi" dokładnie \(\displaystyle{ d}\) krawędzi.
Rozstrzygnąć, dla jakich \(\displaystyle{ d}\) oraz \(\displaystyle{ n\in\{d+1,d+2,...,2d+1\}}\) istnieją grafy \(\displaystyle{ d}\)-regularne o dokładnie \(\displaystyle{ n}\) wierzchołkach.
Wszystkie wyniki są mile widziane. Na rozgrzewkę można zacząć od \(\displaystyle{ }\)n=d, lub \(\displaystyle{ n=2d}\).
(Można też rozważac \(\displaystyle{ n}\) większe od \(\displaystyle{ 2d+1}\).)
Grafy regularne, istnienie
-
Dumel
- Użytkownik
- Posty: 2000
- Rejestracja: 19 lut 2008, o 17:35
- Płeć: Mężczyzna
- Lokalizacja: Stare Pole/Kraków
- Podziękował: 60 razy
- Pomógł: 202 razy
Grafy regularne, istnienie
dla parzystych \(\displaystyle{ d}\) każda liczba \(\displaystyle{ n \ge d+1}\) spełnia warunki zadania:
ustawmy sobie wierzchołki grafu w wierzchołkach \(\displaystyle{ n}\) kąta foremnego. rozważmy okrąg opisany na tym wielokącie. jest on podzielony na \(\displaystyle{ n}\) równych części o powiedzmy długości 1. teraz między wierzchołkami a i b ciągniemy krawędź jeśli ich odległość mierzona po łuku jest niezerowa oraz \(\displaystyle{ \le \frac{d}{2}}\) i gotowe.
dla nieparzystych \(\displaystyle{ d}\) też łatwo idzie:
musi zachodzić podzielność \(\displaystyle{ 2|nd}\) więc \(\displaystyle{ n}\) musi być parzyste i oczywiście \(\displaystyle{ \ge d+1}\). są to warunki konieczne i jak zaraz udowodnię dostateczne. analogicznie jak poprzednio budujemy \(\displaystyle{ n}\)-kąt foremny. krawędz miedzy wierzchołkami a i b ciągniemy gdy ich odległość mierzona po łuku jest niezerowa i \(\displaystyle{ \le \frac{d-1}{2}}\) lub gdy są one symetryczne względem środka okręgu opisanego.
(te konstrukcje działają, bo opisane relacje tj. odległość i symetria są symetryczne)
ustawmy sobie wierzchołki grafu w wierzchołkach \(\displaystyle{ n}\) kąta foremnego. rozważmy okrąg opisany na tym wielokącie. jest on podzielony na \(\displaystyle{ n}\) równych części o powiedzmy długości 1. teraz między wierzchołkami a i b ciągniemy krawędź jeśli ich odległość mierzona po łuku jest niezerowa oraz \(\displaystyle{ \le \frac{d}{2}}\) i gotowe.
dla nieparzystych \(\displaystyle{ d}\) też łatwo idzie:
musi zachodzić podzielność \(\displaystyle{ 2|nd}\) więc \(\displaystyle{ n}\) musi być parzyste i oczywiście \(\displaystyle{ \ge d+1}\). są to warunki konieczne i jak zaraz udowodnię dostateczne. analogicznie jak poprzednio budujemy \(\displaystyle{ n}\)-kąt foremny. krawędz miedzy wierzchołkami a i b ciągniemy gdy ich odległość mierzona po łuku jest niezerowa i \(\displaystyle{ \le \frac{d-1}{2}}\) lub gdy są one symetryczne względem środka okręgu opisanego.
(te konstrukcje działają, bo opisane relacje tj. odległość i symetria są symetryczne)