Prezentacja multimedialna

Polecenie 1

Zapoznaj się z prezentacją przedstawiającą algorytm, którego zadaniem jest znalezienie w reprezentowanym przez macierz sąsiedztwa grafie nieskierowanym cyklu oraz ścieżki Hamiltona.

RMICu7IligKjS1

Przykład 1

Graf analizowany przez Hamiltona:

RGVGmHJNxcAfz

Ilustracja przedstawia pięciokąt wypukły. Jego wierzchołki są oznaczone kolejno cyframi 4, 0, 1, 2, 5. Wierzchołek 4 oraz 1 jest połączony przekątną, tak samo jak wierzchołek 2 i 0. Z wierzchołka 4 oraz 2 wychodzą proste, które spotykają się w punkcie oznaczonym 3, który znajduje się wewnątrz figury. Wszystkie wierzchołki i punkty są oznaczone niebieskimi kółkami. — Graf spójny nieskierowany, który składa się z 20 wierzchołków i XXX krawędzi.
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Macierz sąsiedztwa grafu:

Linia 1. const int n znak równości 20 średnik. Linia 3. int macierzSasiedztwa otwórz nawias kwadratowy n zamknij nawias kwadratowy otwórz nawias kwadratowy n zamknij nawias kwadratowy znak równości otwórz nawias klamrowy. Linia 4. otwórz nawias klamrowy 0 przecinek 1 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik Wierzchołek 0. Linia 5. otwórz nawias klamrowy 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik Wierzchołek 1. Linia 6. otwórz nawias klamrowy 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik Wierzchołek 2. Linia 7. otwórz nawias klamrowy 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik Wierzchołek 3. Linia 8. otwórz nawias klamrowy 1 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik Wierzchołek 4. Linia 9. otwórz nawias klamrowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik Wierzchołek 5. Linia 10. otwórz nawias klamrowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik Wierzchołek 6. Linia 11. otwórz nawias klamrowy 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik Wierzchołek 7. Linia 12. otwórz nawias klamrowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik Wierzchołek 8. Linia 13. otwórz nawias klamrowy 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik Wierzchołek 9. Linia 14. otwórz nawias klamrowy 0 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik Wierzchołek 10. Linia 15. otwórz nawias klamrowy 0 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik Wierzchołek 11. Linia 16. otwórz nawias klamrowy 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik Wierzchołek 12. Linia 17. otwórz nawias klamrowy 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik Wierzchołek 13. Linia 18. otwórz nawias klamrowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik Wierzchołek 14. Linia 19. otwórz nawias klamrowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik Wierzchołek 15. Linia 20. otwórz nawias klamrowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik Wierzchołek 16. Linia 21. otwórz nawias klamrowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik Wierzchołek 17. Linia 22. otwórz nawias klamrowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 zamknij nawias klamrowy przecinek prawy ukośnik prawy ukośnik Wierzchołek 18. Linia 23. otwórz nawias klamrowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 1 przecinek 0 zamknij nawias klamrowy prawy ukośnik prawy ukośnik Wierzchołek 19. Linia 24. zamknij nawias klamrowy średnik.

const int n = 20;

int macierzSasiedztwa[n][n] = {
    {0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // Wierzchołek 0
    {1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // Wierzchołek 1
    {0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // Wierzchołek 2
    {0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0}, // Wierzchołek 3
    {1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // Wierzchołek 4
    {0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0}, // Wierzchołek 5
    {0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0}, // Wierzchołek 6
    {1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // Wierzchołek 7
    {0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0}, // Wierzchołek 8
    {0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // Wierzchołek 9
    {0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0}, // Wierzchołek 10
    {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0}, // Wierzchołek 11
    {0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0}, // Wierzchołek 12
    {0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0}, // Wierzchołek 13
    {0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0}, // Wierzchołek 14
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0}, // Wierzchołek 15
    {0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0}, // Wierzchołek 16
    {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0}, // Wierzchołek 17
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1}, // Wierzchołek 18
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0}  // Wierzchołek 19
};

Wynik działania programu dla grafu analizowanego przez Hamiltona:

Graf zawiera cykl Hamiltona
Przykladowy cykl Hamiltona: 0 1 2 3 4 5 6 16 17 18 19 15 14 13 12 11 10 9 8 7 0

Polecenie 2

R1amPKBJWq8o1

Polecenie 3

RkJMJQWFzdhPh

Polecenie 4

RTPY7CcOJj9dJ

Przeczytaj

Sprawdź się