Ile wierzchołków może mieć graf regularny stopnia \(\displaystyle{ > 2}\), który ma \(\displaystyle{ 2014}\) wierzchołków?
Z zadania wynika, że wierchołki w grafie są połączone wg zasady "każdy z każdym". W grafie regularnym jest \(\displaystyle{ \frac{n(n-1)}{2}}\) krawędzi. Zatem można napisać, że:
\(\displaystyle{ 2014 = \frac{n(n-1)}{2}}\)
Jednak jest taki problem, że delta równania kwadratowego, które powstaje:
\(\displaystyle{ n(n-1)=4028}\)
nie jest liczbą naturalną, a nie może być np. pół wierzchołka. Co może być źle?
Liczba wierzchołków w grafie regularnym
-
- Użytkownik
- Posty: 86
- Rejestracja: 7 wrz 2013, o 16:18
- Płeć: Mężczyzna
- Lokalizacja: Gdańsk
- Podziękował: 14 razy
-
- Użytkownik
- Posty: 59
- Rejestracja: 2 gru 2014, o 18:25
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 1 raz
- Pomógł: 17 razy
Liczba wierzchołków w grafie regularnym
\(\displaystyle{ \frac{n(n-1)}{2}}\) krawędzi to jest w grafie pełnym (który, swoją drogą, też jest regularny, \(\displaystyle{ n-1}\)-regularny), ale w grafie regularnym, w którym każdy wierzchołek jest stopnia \(\displaystyle{ r}\), jest \(\displaystyle{ \frac{r \cdot n}{2}}\) krawędzi (każda krawędź łączy dwa wierzchołki, z każdego wierzchołka wychodzi \(\displaystyle{ r}\) krawędzi), więc musisz szukać takich \(\displaystyle{ r}\) oraz \(\displaystyle{ n}\), że zachodzi \(\displaystyle{ \frac{n \cdot r}{2} = 2014}\).