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
Składowe spójności
-
- Użytkownik
- Posty: 39
- Rejestracja: 2 paź 2009, o 14:35
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 8 razy
-
- 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
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.
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.