Sprawdź się

Pokaż ćwiczenia:

RNVa0NhXq8NyP1

Ćwiczenie 1

R1OLtZSXBenym1

Ćwiczenie 2

RPTp6CWxo9mal2

Ćwiczenie 3

Spisano kilka ciągów stopni wszystkich wierzchołków grafu. Który z grafów zawiera cykl Eulera? Możliwe odpowiedzi: 1. 4 6 4 2 2 4 2, 2. 2 3 5 4 6 7 8 9 8, 3. 2 4 4 4 4 6 2, 4. 2 2 2 2 2 2 2 2

R1bmsrx8j3wba2

Ćwiczenie 4

Źródło: Contentplus.pl sp. z o.o., licencja: CC BY-SA 3.0.

Ćwiczenie 5

RZh784LreTXsC2

Graf, który posiada V wierzchołków i V+1 krawędzi może posiadać cykl Eulera. Możliwe odpowiedzi: 1. Fałsz, 2. Prawda

Ćwiczenie 6

Napisz algorytm sprawdzający, czy w danym grafie spójnym reprezentowanym przez macierz incydencji znajduje się ścieżka Eulera.

Rozwiązanie przetestuj dla grafu reprezentującego mosty królewieckie, uwzględnij następującą macierz incydencji:

$[\begin{matrix} 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 \end{matrix}]$

Specyfikacja problemu:

Dane:

macierzIncydencji – macierz sąsiedztwa grafu; lista list, których elementy przyjmują wartości 0 lub 1

Wynik:

komunikat dotyczący tego, czy graf zawiera ścieżkę Eulera

R1HlE6s6PQUoa

Ćwiczenie 7

Napisz algorytm sprawdzający, czy w danym grafie spójnym reprezentowanym przez macierz incydencji znajduje się cykl Eulera.

Rozwiązanie przetestuj dla grafu reprezentującego mosty królewieckie, uwzględnij następującą macierz incydencji:

$[\begin{matrix} 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 \end{matrix}]$

Specyfikacja problemu:

Dane:

macierzIncydencji – macierz incydencji grafu; lista list, których elementy przyjmują wartości 0 lub 1

Wynik:

komunikat dotyczący tego, czy graf zawiera cykl Eulera

RqnaOpMvWIuY8

funkcja istnienieCykluEulera(macierzIncydencji):
	liczbaWierzcholkow ← długość(macierzIncydencji)
    stopnieWierzcholkow ← utwórz pustą tablicę o długości liczbaWierzcholkow
    liczbaNieparzystych ← 0

    dla i = 0, 1, ..., liczbaWierzcholkow - 1 wykonuj:
        dla j = 0, 1, ..., liczbaWierzcholkow - 1 wykonuj:
            stopnieWierzcholkow[i] ← stopnieWierzcholkow[i] + macierzIncydencji[i][j]

   dla i = 0, 1, ..., liczbaWierzcholkow - 1 wykonuj:
        jeżeli stopnieWierzcholkow[i] mod 2 != 0:
            liczbaNieparzystych += 1

    jeżeli liczbaNieparzystych == 0 ORAZ liczbaWierzcholkow > 0:
        wypisz "Graf zawiera cykl Eulera."
    w przeciwnym razie:
        wypisz "Graf nie zawiera cyklu Eulera."

RsQ9qx7XRLBdr3

Ćwiczenie 8

Aplet

Dla nauczyciela