szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 14 wrz 2015, o 19:29 
Użytkownik

Posty: 86
Lokalizacja: Gdańsk
Ile wierzchołków może mieć graf regularny stopnia > 2, który ma 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 \frac{n(n-1)}{2} krawędzi. Zatem można napisać, że:

2014 = \frac{n(n-1)}{2}

Jednak jest taki problem, że delta równania kwadratowego, które powstaje:
n(n-1)=4028

nie jest liczbą naturalną, a nie może być np. pół wierzchołka. Co może być źle?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna Offline
PostNapisane: 14 wrz 2015, o 23:04 
Użytkownik
Avatar użytkownika

Posty: 1202
2014?...
Góra
Mężczyzna Offline
PostNapisane: 14 wrz 2015, o 23:26 
Użytkownik

Posty: 59
Lokalizacja: Polska
\frac{n(n-1)}{2} krawędzi to jest w grafie pełnym (który, swoją drogą, też jest regularny, n-1-regularny), ale w grafie regularnym, w którym każdy wierzchołek jest stopnia r, jest \frac{r \cdot n}{2} krawędzi (każda krawędź łączy dwa wierzchołki, z każdego wierzchołka wychodzi r krawędzi), więc musisz szukać takich r oraz n, że zachodzi \frac{n \cdot r}{2} = 2014.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 liczba par zbiorów  MikolajB  3
 Liczba kombinacji  poosheck  2
 liczba podzbiorów - zadanie 3  celia11  3
 Dowód nierówności w grafie  Fray  4
 Ile razy liczba k występuje w przedziale  Aga2909  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl