Składowe spójności

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
czarny1989
Użytkownik
Użytkownik
Posty: 39
Rejestracja: 2 paź 2009, o 14:35
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 8 razy

Składowe spójności

Post autor: czarny1989 »

Siemka.
Mam proste zadanie:
Graf prosty składa się z trzech składowych spójności. Pierwsza z nich zbudowana jest na \(\displaystyle{ 3}\), druga na \(\displaystyle{ 5}\) a trzecia na \(\displaystyle{ 7}\) wierzchołkach. Ile maksymalnie krawędzi może wystąpić w tym grafie?

Znalazłem taką definicję:

Graf prosty \(\displaystyle{ G = (V, E)}\) taki że \(\displaystyle{ |V| = n}\) mający \(\displaystyle{ k}\) składowych spójności może mieć co najwyżej
\(\displaystyle{ \frac{\left( n - k \right) \cdot \left( n - k + 1 \right)}{2}}\) krawędzi.

Po podstawieniu do wzoru wychodzi mi oto taki wynik:
\(\displaystyle{ \frac{\left( 15 - 3 \right) \cdot \left( 15 - 3 + 1 \right)}{2}}\)

\(\displaystyle{ \frac{12 \cdot 13}{2} = 76}\)

Czy dobrze zrozumiałem treść zadania i dobrze podstawiłem pod wzór?
Pozdrawiam,
czarny1989
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

Składowe spójności

Post autor: »

To co znalazłeś to nie definicja tylko twierdzenie. Twierdzenie którego sensu nie zrozumiałeś - nie jest wcale powiedziane, że maksymalna liczba \(\displaystyle{ 78}\) wierzchołków jest realizowana dla grafu o którym mowa w zadaniu (i wcale tak nie jest).

Matematyka to nie podstawianie do wzorów.

Wskazówka: graf o którym mowa w zadaniu będzie miał maksymalną liczbę wierzchołków, jeśli każda spójna składowa (czy jak wolisz: składowa spójności) będzie grafem pełnym (każda para wierzchołków połączona krawędzią).

Q.
ODPOWIEDZ