R2JB51E5RABJ7
Zdjęcie przedstawia cienką niebieską siatkę na ciemnym tle.

I_R_W14_M41C_C++ Grafy dla wytrwałych

Źródło: Uriel SC, domena publiczna.
Już wiesz
  • Potrafisz omówić problem mostów królewieckich.

  • Czy w danych grafach możliwe jest znalezienie cyklu Eulera.

  • Jak dokonać analizy algorytmu sprawdzającego, czy dany graf jest eulerowski lub półeulerowski.

Teraz czas, aby sprawdzić wiedzę i umiejętności w praktyce.

RN3FZ5PNPKODF
Ćwiczenie 1
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
RRRR3DM7SJEBA
Ćwiczenie 2
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
R1QSNX3AFCDTC
Ćwiczenie 3
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Źródło: Contentplus.pl sp. z o.o., licencja: CC BY-SA 3.0.
Ćwiczenie 4
R1PQC9HCZRE5A
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 5

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:

01101101001101000011

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

RSRG9E1VO8CAQ
Przekształć algorytm sprawdzający czy w danym grafie spójnym znajduje się cykl Eulera tak, aby działał na macierzy sąsiedztwa. (Uzupełnij).