Strefa wyzwań - PYI_R_W14_M41C Grafy dla wytrwałych

RQCC32OC8CXK3

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.

RE2UQT7NQA78G

Ćwiczenie 1

R1BUR7L573NOL

Ć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

RAFJVP14VT2M7

Ćwiczenie 3

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

Ćwiczenie 4

RKJAE3RMRRBVF

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

RqMUv4CAn0eiK

Ćwiczenie 5

Ile spójnych składowych może mieć graf nieskierowany bez pętli i krwędzi wielokrotnych o 6 wierzchołkach i następującym ciągu stopni wierzchołków.

2, 2, 2, 2, 2, 2 Możliwe odpowiedzi: 1. 1, 2. 2, 3. 3, 4. 6

R34xTehBMxpYX

Ćwiczenie 6

RobNyF0oGKt0S1

Ćwiczenie 7

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

Ćwiczenie 8

Napisz program, który obliczy liczbę spójnych składowych grafu nieskierowanego, a następnie ją wyświetli.

Specyfikacja problemu:

Dane:

macierzSasiedztwa – macierz sąsiedztwa grafu; lista dwuwymiarowa liczb naturalnych

Wynik:

liczba spójnych składowych grafu; liczba naturalna

Działanie programu przetestuj dla następujących danych:

Graf:

RHBbzJCeoL0tO

Macierz sąsiedztwa tego grafu:

macierz_sasiedztwa = [
    [0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 1, 0],
    [0, 1, 0, 1, 0, 0],
    [0, 0, 1, 0, 1, 0],
    [0, 1, 0, 1, 0, 0],
    [0, 0, 0, 0, 0, 0]
]

Przykładowy wynik dla podanych danych:

Liczba spojnych skladowych grafu: 3

R1Gw013JDcmB3

Linia 1. macierz podkreślnik sasiedztwa znak równości otwórz nawias kwadratowy. Linia 2. otwórz nawias kwadratowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias kwadratowy przecinek. Linia 3. otwórz nawias kwadratowy 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 zamknij nawias kwadratowy przecinek. Linia 4. otwórz nawias kwadratowy 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 zamknij nawias kwadratowy przecinek. Linia 5. otwórz nawias kwadratowy 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 zamknij nawias kwadratowy przecinek. Linia 6. otwórz nawias kwadratowy 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 zamknij nawias kwadratowy przecinek. Linia 7. otwórz nawias kwadratowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias kwadratowy. Linia 8. zamknij nawias kwadratowy. Linia 10. n znak równości len otwórz nawias okrągły macierz podkreślnik sasiedztwa zamknij nawias okrągły. Linia 12. def przeszukaj otwórz nawias okrągły v przecinek odwiedzone przecinek macierz podkreślnik sasiedztwa zamknij nawias okrągły dwukropek. Linia 13. odwiedzone otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości True. Linia 14. for i in range otwórz nawias okrągły len otwórz nawias okrągły macierz podkreślnik sasiedztwa zamknij nawias okrągły zamknij nawias okrągły dwukropek. Linia 15. if macierz podkreślnik sasiedztwa otwórz nawias kwadratowy v zamknij nawias kwadratowy otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości znak równości 1 and not odwiedzone otwórz nawias kwadratowy i zamknij nawias kwadratowy dwukropek. Linia 16. przeszukaj otwórz nawias okrągły i przecinek odwiedzone przecinek macierz podkreślnik sasiedztwa zamknij nawias okrągły. Linia 18. def liczba podkreślnik skladowych otwórz nawias okrągły macierz podkreślnik sasiedztwa zamknij nawias okrągły dwukropek. Linia 19. odwiedzone znak równości otwórz nawias kwadratowy False zamknij nawias kwadratowy asterysk len otwórz nawias okrągły macierz podkreślnik sasiedztwa zamknij nawias okrągły. Linia 20. licznik podkreślnik skladowych znak równości 0. Linia 22. for i in range otwórz nawias okrągły len otwórz nawias okrągły macierz podkreślnik sasiedztwa zamknij nawias okrągły zamknij nawias okrągły dwukropek. Linia 23. if not odwiedzone otwórz nawias kwadratowy i zamknij nawias kwadratowy dwukropek. Linia 24. przeszukaj otwórz nawias okrągły i przecinek odwiedzone przecinek macierz podkreślnik sasiedztwa zamknij nawias okrągły. Linia 25. licznik podkreślnik skladowych plus znak równości 1. Linia 27. return licznik podkreślnik skladowych. Linia 29. print otwórz nawias okrągły cudzysłów Liczba spojnych skladowych grafu dwukropek cudzysłów przecinek liczba podkreślnik skladowych otwórz nawias okrągły macierz podkreślnik sasiedztwa zamknij nawias okrągły zamknij nawias okrągły.

macierz_sasiedztwa = [
    [0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 1, 0],
    [0, 1, 0, 1, 0, 0],
    [0, 0, 1, 0, 1, 0],
    [0, 1, 0, 1, 0, 0],
    [0, 0, 0, 0, 0, 0]
]

n = len(macierz_sasiedztwa)
    
def przeszukaj(v, odwiedzone, macierz_sasiedztwa):
    odwiedzone[v] = True
    for i in range(len(macierz_sasiedztwa)):
        if macierz_sasiedztwa[v][i] == 1 and not odwiedzone[i]:
            przeszukaj(i, odwiedzone, macierz_sasiedztwa)

def liczba_skladowych(macierz_sasiedztwa):
    odwiedzone = [False] * len(macierz_sasiedztwa)
    licznik_skladowych = 0

    for i in range(len(macierz_sasiedztwa)):
        if not odwiedzone[i]:
            przeszukaj(i, odwiedzone, macierz_sasiedztwa)
            licznik_skladowych += 1

    return licznik_skladowych

print("Liczba spojnych skladowych grafu:", liczba_skladowych(macierz_sasiedztwa))

Ćwiczenie 9

Napisz program, który sprawdzi, czy dana para wierzchołków o indeksach v oraz w tworzących krawędź vw grafu spójnego nieskierowanego reprezentowanego przez macierz sąsiedztwa jest mostem.

Specyfikacja problemu:

Dane:

macierzSasiedztwa – macierz sąsiedztwa grafu; lista dwuwymiarowa liczb naturalnych
v – indeks wierzchołka tworzącego krawędź; liczba naturalna
w – indeks wierzchołka tworzącego krawędź; liczba naturalna

Wynik:

komunikat informujący o tym, czy krawędź tworzona przez dwa podane wierzchołki vw jest mostem

Działanie programu przetestuj dla następujących danych:

Graf:

RiOppoLhKXNb6

Macierz sąsiedztwa grafu:

macierz_sasiedztwa = [
    [0, 1, 0, 1, 0, 0, 0, 1],
    [1, 0, 1, 1, 0, 0, 0, 0],
    [0, 1, 0, 0, 1, 0, 0, 0],
    [1, 1, 0, 0, 1, 0, 0, 0],
    [0, 0, 1, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 1, 0]
]

v = 0
w = 7

Przykładowy wynik dla podanych danych:

Krawedz 0-7 jest mostem

RAX4M2jwivnuO

Linia 1. macierz podkreślnik sasiedztwa znak równości otwórz nawias kwadratowy. Linia 2. otwórz nawias kwadratowy 0 przecinek 1 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 1 zamknij nawias kwadratowy przecinek. Linia 3. otwórz nawias kwadratowy 1 przecinek 0 przecinek 1 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias kwadratowy przecinek. Linia 4. otwórz nawias kwadratowy 0 przecinek 1 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 zamknij nawias kwadratowy przecinek. Linia 5. otwórz nawias kwadratowy 1 przecinek 1 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 0 przecinek 0 zamknij nawias kwadratowy przecinek. Linia 6. otwórz nawias kwadratowy 0 przecinek 0 przecinek 1 przecinek 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias kwadratowy przecinek. Linia 7. otwórz nawias kwadratowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 zamknij nawias kwadratowy przecinek. Linia 8. otwórz nawias kwadratowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 przecinek 1 zamknij nawias kwadratowy przecinek. Linia 9. otwórz nawias kwadratowy 1 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 1 przecinek 0 zamknij nawias kwadratowy. Linia 10. zamknij nawias kwadratowy. Linia 12. v znak równości 0. Linia 13. w znak równości 7. Linia 15. n znak równości len otwórz nawias okrągły macierz podkreślnik sasiedztwa zamknij nawias okrągły. Linia 17. def przeszukaj otwórz nawias okrągły v przecinek odwiedzone przecinek macierz podkreślnik sasiedztwa zamknij nawias okrągły dwukropek. Linia 18. odwiedzone otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości True. Linia 19. for i in range otwórz nawias okrągły len otwórz nawias okrągły macierz podkreślnik sasiedztwa zamknij nawias okrągły zamknij nawias okrągły dwukropek. Linia 20. if macierz podkreślnik sasiedztwa otwórz nawias kwadratowy v zamknij nawias kwadratowy otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości znak równości 1 and not odwiedzone otwórz nawias kwadratowy i zamknij nawias kwadratowy dwukropek. Linia 21. przeszukaj otwórz nawias okrągły i przecinek odwiedzone przecinek macierz podkreślnik sasiedztwa zamknij nawias okrągły. Linia 23. def liczba podkreślnik skladowych otwórz nawias okrągły macierz podkreślnik sasiedztwa zamknij nawias okrągły dwukropek. Linia 25. odwiedzone znak równości otwórz nawias kwadratowy False zamknij nawias kwadratowy asterysk n. Linia 26. licznik podkreślnik skladowych znak równości 0. Linia 28. for i in range otwórz nawias okrągły n zamknij nawias okrągły dwukropek. Linia 29. if not odwiedzone otwórz nawias kwadratowy i zamknij nawias kwadratowy dwukropek. Linia 30. przeszukaj otwórz nawias okrągły i przecinek odwiedzone przecinek macierz podkreślnik sasiedztwa zamknij nawias okrągły. Linia 31. licznik podkreślnik skladowych plus znak równości 1. Linia 33. return licznik podkreślnik skladowych. Linia 35. def czy podkreślnik most otwórz nawias okrągły v przecinek w przecinek macierz podkreślnik sasiedztwa zamknij nawias okrągły dwukropek. Linia 36. macierz podkreślnik sasiedztwa otwórz nawias kwadratowy v zamknij nawias kwadratowy otwórz nawias kwadratowy w zamknij nawias kwadratowy znak równości 0. Linia 37. macierz podkreślnik sasiedztwa otwórz nawias kwadratowy w zamknij nawias kwadratowy otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości 0. Linia 38. nowa podkreślnik liczba znak równości liczba podkreślnik skladowych otwórz nawias okrągły macierz podkreślnik sasiedztwa zamknij nawias okrągły. Linia 39. macierz podkreślnik sasiedztwa otwórz nawias kwadratowy v zamknij nawias kwadratowy otwórz nawias kwadratowy w zamknij nawias kwadratowy znak równości 1. Linia 40. macierz podkreślnik sasiedztwa otwórz nawias kwadratowy w zamknij nawias kwadratowy otwórz nawias kwadratowy v zamknij nawias kwadratowy znak równości 1. Linia 41. liczba znak równości liczba podkreślnik skladowych otwórz nawias okrągły macierz podkreślnik sasiedztwa zamknij nawias okrągły. Linia 43. return liczba wykrzyknik znak równości nowa podkreślnik liczba. Linia 45. wynik znak równości cudzysłów Krawedz cudzysłów plus str otwórz nawias okrągły v zamknij nawias okrągły plus cudzysłów minus cudzysłów plus str otwórz nawias okrągły w zamknij nawias okrągły plus cudzysłów cudzysłów. Linia 46. if czy podkreślnik most otwórz nawias okrągły v przecinek w przecinek macierz podkreślnik sasiedztwa zamknij nawias okrągły dwukropek. Linia 47. wynik plus znak równości cudzysłów jest mostem cudzysłów. Linia 48. else dwukropek. Linia 49. wynik plus znak równości cudzysłów nie jest mostem cudzysłów. Linia 51. print otwórz nawias okrągły wynik zamknij nawias okrągły.

macierz_sasiedztwa = [
    [0, 1, 0, 1, 0, 0, 0, 1],
    [1, 0, 1, 1, 0, 0, 0, 0],
    [0, 1, 0, 0, 1, 0, 0, 0],
    [1, 1, 0, 0, 1, 0, 0, 0],
    [0, 0, 1, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 1, 0]
]

v = 0
w = 7

n = len(macierz_sasiedztwa)

def przeszukaj(v, odwiedzone, macierz_sasiedztwa):
    odwiedzone[v] = True
    for i in range(len(macierz_sasiedztwa)):
        if macierz_sasiedztwa[v][i] == 1 and not odwiedzone[i]:
            przeszukaj(i, odwiedzone, macierz_sasiedztwa)

def liczba_skladowych(macierz_sasiedztwa):
    
    odwiedzone = [False] * n
    licznik_skladowych = 0

    for i in range(n):
        if not odwiedzone[i]:
            przeszukaj(i, odwiedzone, macierz_sasiedztwa)
            licznik_skladowych += 1

    return licznik_skladowych

def czy_most(v, w, macierz_sasiedztwa):
    macierz_sasiedztwa[v][w] = 0
    macierz_sasiedztwa[w][v] = 0
    nowa_liczba = liczba_skladowych(macierz_sasiedztwa)
    macierz_sasiedztwa[v][w] = 1
    macierz_sasiedztwa[w][v] = 1
    liczba = liczba_skladowych(macierz_sasiedztwa)

    return liczba != nowa_liczba

wynik = "Krawedz " + str(v) + "-" + str(w) + " "
if czy_most(v, w, macierz_sasiedztwa):
    wynik += "jest mostem"
else:
    wynik += "nie jest mostem"

print(wynik)

Stopnie grafu - implementacja

PYI_R_W14_M41C Grafy dla wytrwałych