Wymyśl pytanie na kartkówkę związane z tematem materiału.
Wymyśl pytanie na kartkówkę związane z tematem materiału.
RKaxxqCU867J71
Ćwiczenie 2
Wymyśl pytanie na kartkówkę związane z tematem materiału.
Wymyśl pytanie na kartkówkę związane z tematem materiału.
Ćwiczenie 2
Uzupełnij tabelę będącą macierzą sąsiedztwa grafu, którego macierz incydencji ma następującą postać: A równa się, w macierzy zapisano: Linia 1: zero, zero, jeden, jeden, zero. Linia 2: zero, zero, zero, jeden, jeden. Linia 3: jeden, zero, zero, jeden, jeden. Linia 4: jeden, jeden, jeden, zero, jeden. Linia 5: zero, jeden, jeden, jeden, zero.
R5kpLuCgI7RXv
RB5qE0QT2xJzo1
Ćwiczenie 3
Połącz w pary reprezentację z jej rozmiarem. Maicerz sąsiedztwa Możliwe odpowiedzi: 1. zależy od stopnia każdego wierzchołka, 2. par dwóch elementów, 3. , 4. Lista sąsiedztwa Możliwe odpowiedzi: 1. zależy od stopnia każdego wierzchołka, 2. par dwóch elementów, 3. , 4. Macierz incydencji Możliwe odpowiedzi: 1. zależy od stopnia każdego wierzchołka, 2. par dwóch elementów, 3. , 4. Lista krawędzi Możliwe odpowiedzi: 1. zależy od stopnia każdego wierzchołka, 2. par dwóch elementów, 3. , 4.
Połącz w pary reprezentację z jej rozmiarem. Maicerz sąsiedztwa Możliwe odpowiedzi: 1. zależy od stopnia każdego wierzchołka, 2. par dwóch elementów, 3. , 4. Lista sąsiedztwa Możliwe odpowiedzi: 1. zależy od stopnia każdego wierzchołka, 2. par dwóch elementów, 3. , 4. Macierz incydencji Możliwe odpowiedzi: 1. zależy od stopnia każdego wierzchołka, 2. par dwóch elementów, 3. , 4. Lista krawędzi Możliwe odpowiedzi: 1. zależy od stopnia każdego wierzchołka, 2. par dwóch elementów, 3. , 4.
RnInxEeBGjbfJ2
Ćwiczenie 4
Zaznacz każde zdanie prawdziwe. Możliwe odpowiedzi: 1. W grafie niezawierającym pętli i krawędzi wielokrotnych suma liczb elementów liczby sąsiadów w każdej liście sąsiadów jest zawsze parzysta., 2. W macierzy sąsiedztwa wiersz odpowiadający wierzchołkowi stopnia zerowego ma same zera., 3. Macierz sąsiedztwa niektórych przypadkach może mieć rozmiar ., 4. Suma wszystkich jedynek w macierzy sąsiedztwa jest równa podwojonej liczbie krawędzi.
R1ANMnAUVvngZ2
Ćwiczenie 5
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
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 5
RPiTPEp4hCX3p
R13IwlG5Aj9Uq21
Ćwiczenie 6
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
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.
31
Ćwiczenie 7
Dany jest graf nieskierowany bez wag. Napisz program, która przekształci macierz sąsiedztwa tego grafu w listę sąsiedztwa.
Specyfikacja problemu:
Dane:
macierz_sasiedztw – macierz liczb całkowitych
Wynik:
lista sąsiedztwa grafu
Przykładowe wyniki:
Linia 1. 0 dwukropek 1 2 3 4.
Linia 2. 1 dwukropek 0 2 3 4.
Linia 3. 2 dwukropek 0 1 4.
Linia 4. 3 dwukropek 0 1 4.
Linia 5. 4 dwukropek 0 1 2 3.
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Przykładowe rozwiązanie zadania:
Linia 1. n znak równości 5.
Linia 2. E znak równości 10.
Linia 4. lista podkreślnik sasiedztwa znak równości otwórz nawias kwadratowy.
Linia 5. otwórz nawias kwadratowy 1 przecinek 2 przecinek 3 przecinek 4 zamknij nawias kwadratowy przecinek.
Linia 6. otwórz nawias kwadratowy 0 przecinek 2 przecinek 3 przecinek 4 zamknij nawias kwadratowy przecinek.
Linia 7. otwórz nawias kwadratowy 0 przecinek 1 przecinek 4 zamknij nawias kwadratowy przecinek.
Linia 8. otwórz nawias kwadratowy 0 przecinek 1 przecinek 4 zamknij nawias kwadratowy przecinek.
Linia 9. otwórz nawias kwadratowy 0 przecinek 1 przecinek 2 przecinek 3 zamknij nawias kwadratowy.
Linia 10. zamknij nawias kwadratowy.
Linia 12. macierz podkreślnik incydencji znak równości otwórz nawias kwadratowy otwórz nawias kwadratowy 0 for podkreślnik in range otwórz nawias okrągły E zamknij nawias okrągły zamknij nawias kwadratowy for podkreślnik in range otwórz nawias okrągły n zamknij nawias okrągły zamknij nawias kwadratowy.
Linia 14. m znak równości 0.
Linia 16. def przeksztalc otwórz nawias okrągły macierz podkreślnik incydencji zamknij nawias okrągły dwukropek.
Linia 17. global m.
Linia 18. for i in range otwórz nawias okrągły n zamknij nawias okrągły dwukropek.
Linia 19. for j in lista podkreślnik sasiedztwa otwórz nawias kwadratowy i zamknij nawias kwadratowy dwukropek.
Linia 20. if i zamknij nawias ostrokątny j dwukropek.
Linia 21. continue.
Linia 23. macierz podkreślnik incydencji otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy m zamknij nawias kwadratowy znak równości 1.
Linia 24. macierz podkreślnik incydencji otwórz nawias kwadratowy j zamknij nawias kwadratowy otwórz nawias kwadratowy m zamknij nawias kwadratowy znak równości 1.
Linia 25. m plus znak równości 1.
Linia 27. def wypisz otwórz nawias okrągły macierz podkreślnik incydencji zamknij nawias okrągły dwukropek.
Linia 28. for i in range otwórz nawias okrągły n zamknij nawias okrągły dwukropek.
Linia 29. for j in range otwórz nawias okrągły m zamknij nawias okrągły dwukropek.
Linia 30. print otwórz nawias okrągły macierz podkreślnik incydencji otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy j zamknij nawias kwadratowy przecinek end znak równości cudzysłów cudzysłów zamknij nawias okrągły.
Linia 31. print otwórz nawias okrągły zamknij nawias okrągły.
Linia 33. przeksztalc otwórz nawias okrągły macierz podkreślnik incydencji zamknij nawias okrągły.
Linia 34. wypisz otwórz nawias okrągły macierz podkreślnik incydencji zamknij nawias okrągły.
n = 5
E = 10
lista_sasiedztwa = [
[1, 2, 3, 4],
[0, 2, 3, 4],
[0, 1, 4],
[0, 1, 4],
[0, 1, 2, 3]
]
macierz_incydencji = [[0 for _ in range(E)] for _ in range(n)]
m = 0
def przeksztalc(macierz_incydencji):
global m
for i in range(n):
for j in lista_sasiedztwa[i]:
if i > j:
continue
macierz_incydencji[i][m] = 1
macierz_incydencji[j][m] = 1
m += 1
def wypisz(macierz_incydencji):
for i in range(n):
for j in range(m):
print(macierz_incydencji[i][j], end=" ")
print()
przeksztalc(macierz_incydencji)
wypisz(macierz_incydencji)
31
Ćwiczenie 9
Macierze sąsiedztwa dobrze sprawdzają się w reprezentacji grafów ważonych. Jeśli wagi krawędzi są różne od 0, wówczas tam, gdzie normalnie wstawilibyśmy 1, wpiszemy wagę krawędzi. Gdyby jednak graf zawierał wagę 0, to za brak połączenia uznajemy pewną liczbę waga rożną od wszystkich wag w grafie.
Podobnie jak macierz sąsiedztwa, także lista sąsiedztwa może służyć do prezentacji grafów ważonych. W takim wypadku wyrazy na liście sąsiadów danego wierzchołka będą parą uporządkowaną dwóch elementów: indeksu sąsiada oraz wagi krawędzi łączącej sąsiada z wierzchołkiem. Przykładowo: jeśli waga krawędzi ij wynosi 5, wówczas na liście listaSasiedztwa[i] powinna znaleźć się para [j, 5]. Graf domyślnie jest nieskierowany, więc analogicznie lista lista_sasiedztwa[j] zawiera parę [i, 5].
R1b8UlEnz7IDA
Ilustracja przedstawia kolaż trzech grafik: pierwsza grafika przedstawia macierz sąsiedztwa druga grafika przedstawia rysunek grafu i trzecia grafika przedstawia listę sąsiedztwa. Na pierwszej grafice widoczna jest macierz sąsiedztwa. Tworzy ją tabelka pięć na pięć kratek. Jej kolumny i rzędy są oznaczone cyframi od 0 do 4. W pierwszym rzędzie wpisano 0, na niebiesko 5, dalej 0, dalej na niebiesko 6, dalej 0, w drugim rzędzie na niebiesko 5,dalej 0, na niebiesko 7, dalej na niebiesko 8, dalej zero 0, w trzecim rzędzie 0, na niebiesko 7, dalej 0, dalej 0, na niebiesko 1, w czwartym rzędzie na niebiesko 6, dalej na niebiesko 8, dalej 0,dalej 0, dalej na niebiesko 3, w piątym rzędzie 0, dalej 0, dalej na niebiesko 1, dalej na niebiesko 3, dalej 0. Druga widoczna grafika przedstawia rysunek graf. W niebieskich otoczkach zaznaczone są liczby: 0, 1, 2, 3, 4. Widoczne połączenia między. 0 połączone jest czarną linią obok której jest 5 z 1 i z 3 czarną linią obok której jest 6. 1 połączone jest czarną linią obok której jest 5 z 0 z 2 czarną linią obok której jest 7 i z 3 czarną linią obok której jest 8. 2 połączone jest czarną linią obok której jest 7 z 1 i z 4 czarną linią obok której jest 1. 4 połączone jest czarną linią obok której jest 1 z 2 i z 3 czarną linią obok której jest 3. 3 połączone jest czarną linią obok której jest 3 z 4 z 0 czarną linią obok której jest 6 i z 1 czarną linią obok której jest 8. Trzecia widoczna grafika przedstawia listę sąsiedztwa. Na grafice widoczne jest pięć wierszy. W pierwszym wierszu w niebieskim kwadracie 0, dalej w tej samej linii w są dwa czarne kwadraty połączone ze sobą. W pierwszym kwadracie jest 1 w drugim w kolorze niebieskim 5. Od tych kwadratów odchodzi strzałka skierowana w prawą stronę do dwóch połączonych czarnych kwadratów. W pierwszym jest 3, a w drugim w kolorze niebieskim 6. W drugim wierszu w niebieskim kwadracie 1, dalej w tej samej linii w są dwa czarne kwadraty połączone ze sobą. W pierwszym kwadracie jest 0 w drugim w kolorze niebieskim 5. Od tych kwadratów odchodzi strzałka skierowana w prawą stronę do dwóch połączonych czarnych kwadratów. W pierwszym jest 2, a w drugim w kolorze niebieskim 7. Od tych kwadratów odchodzi strzałka w prawą stronę do dwóch połączonych kwadratów. W pierwszym jest 3 a w drugim w niebieskim kolorze 8. W trzecim wierszu w niebieskim kwadracie 2, dalej w tej samej linii w są dwa czarne kwadraty połączone ze sobą. W pierwszym kwadracie jest 1 w drugim w kolorze niebieskim 7. Od tych kwadratów odchodzi strzałka skierowana w prawą stronę do dwóch połączonych czarnych kwadratów. W pierwszym jest 4, a w drugim w kolorze niebieskim 1. W czwartym wierszu w niebieskim kwadracie 3, dalej w tej samej linii w są dwa czarne kwadraty połączone ze sobą. W pierwszym kwadracie jest 0 w drugim w kolorze niebieskim 6. Od tych kwadratów odchodzi strzałka skierowana w prawą stronę do dwóch połączonych czarnych kwadratów. W pierwszym jest 1, a w drugim w kolorze niebieskim 8. Od tych kwadratów odchodzi strzałka w prawą stronę do dwóch połączonych kwadratów. W pierwszym jest 4 a w drugim w niebieskim kolorze 3. W piątym wierszu w niebieskim kwadracie 4, dalej w tej samej linii w są dwa czarne kwadraty połączone ze sobą. W pierwszym kwadracie jest 2 w drugim w kolorze niebieskim 1. Od tych kwadratów odchodzi strzałka skierowana w prawą stronę do dwóch połączonych czarnych kwadratów. W pierwszym jest 3, a w drugim w kolorze niebieskim 3.
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.
Zdefiniowano listę krawędzi w postaci listy list składających się z trzech elementów, gdzie pierwszy i ostatni element każdej listy to indeksy sąsiednich wierzchołków, a element środkowy jest wagą krawędzi łączącej te wierzchołki. Twoim zadaniem jest zdefiniowanie następujących funkcji:
Funkcja przeksztalc_krawedzie(krawedzie), która przekształci listę krawedzie w macierz sąsiedztwa macierz_sasiedztwa w wersji ważonej.
Funkcja przeksztalc_macierz(macierz_sasiedztwa), która na podstawie macierzy sąsiedztwa macierz_sasiedztwa wstawi do listy sąsiedztwa lista_sasiedztwa sąsiadów każdego wierzchołka i.