Wstaw poszczególne elementy do odpowiednich grup, według których można je odpowiednio przedstawić za pomocą teorii grafów. Wierzchołki Możliwe odpowiedzi: 1. relacja znajomości, 2. sieć, 3. mapa, 4. osoba, 5. cząsteczka, 6. wiązanie chemiczne, 7. miasto jako punkt na mapie, 8. miasto jako sieć ulic, 9. węzeł, 10. schemat elektroniczny, 11. połączenie komunikacyjne Krawędzie Możliwe odpowiedzi: 1. relacja znajomości, 2. sieć, 3. mapa, 4. osoba, 5. cząsteczka, 6. wiązanie chemiczne, 7. miasto jako punkt na mapie, 8. miasto jako sieć ulic, 9. węzeł, 10. schemat elektroniczny, 11. połączenie komunikacyjne Grafy Możliwe odpowiedzi: 1. relacja znajomości, 2. sieć, 3. mapa, 4. osoba, 5. cząsteczka, 6. wiązanie chemiczne, 7. miasto jako punkt na mapie, 8. miasto jako sieć ulic, 9. węzeł, 10. schemat elektroniczny, 11. połączenie komunikacyjne
Wstaw poszczególne elementy do odpowiednich grup, według których można je odpowiednio przedstawić za pomocą teorii grafów. Wierzchołki Możliwe odpowiedzi: 1. relacja znajomości, 2. sieć, 3. mapa, 4. osoba, 5. cząsteczka, 6. wiązanie chemiczne, 7. miasto jako punkt na mapie, 8. miasto jako sieć ulic, 9. węzeł, 10. schemat elektroniczny, 11. połączenie komunikacyjne Krawędzie Możliwe odpowiedzi: 1. relacja znajomości, 2. sieć, 3. mapa, 4. osoba, 5. cząsteczka, 6. wiązanie chemiczne, 7. miasto jako punkt na mapie, 8. miasto jako sieć ulic, 9. węzeł, 10. schemat elektroniczny, 11. połączenie komunikacyjne Grafy Możliwe odpowiedzi: 1. relacja znajomości, 2. sieć, 3. mapa, 4. osoba, 5. cząsteczka, 6. wiązanie chemiczne, 7. miasto jako punkt na mapie, 8. miasto jako sieć ulic, 9. węzeł, 10. schemat elektroniczny, 11. połączenie komunikacyjne
Rr1Ms9RCTcuGv21
Ćwiczenie 2
Wymyśl pytanie na kartkówkę związane z tematem materiału.
21
Ćwiczenie 3
Napisz funkcję sprawdzającą, czy w grafie reprezentowanym przez listę krawędzi istnieje przekazana jako parametr droga. Działanie programu przetestuj dla następujących danych:
krawedzie – tablica krawędzi w grafie składająca się z par liczb całkowitych
droga1 – tablica liczb całkowitych
droga2 – tablica liczb całkowitych
Wynik:
Program wypisuje True, jeśli droga istnieje, lub False, jeśli nie istnieje.
Przykładowe wyjście:
Linia 1. True.
Linia 2. False.
True
False
RqMr1MNGlEEaB
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.
Linia 1. def znajdz podkreślnik krawedz otwórz nawias okrągły graf przecinek p przecinek q zamknij nawias okrągły dwukropek.
Linia 2. for i przecinek k in enumerate otwórz nawias okrągły graf zamknij nawias okrągły dwukropek.
Linia 3. if k znak równości znak równości otwórz nawias kwadratowy p przecinek q zamknij nawias kwadratowy or k znak równości znak równości otwórz nawias kwadratowy q przecinek p zamknij nawias kwadratowy dwukropek.
Linia 4. return i.
Linia 5. return minus 1.
Linia 7. def znajdz podkreślnik droge otwórz nawias okrągły graf przecinek droga zamknij nawias okrągły dwukropek.
Linia 8. for i przecinek w in enumerate otwórz nawias okrągły droga otwórz nawias kwadratowy dwukropek minus 1 zamknij nawias kwadratowy zamknij nawias okrągły dwukropek.
Linia 9. if znajdz podkreślnik krawedz otwórz nawias okrągły graf przecinek w przecinek droga otwórz nawias kwadratowy i plus 1 zamknij nawias kwadratowy zamknij nawias okrągły znak równości znak równości minus 1 dwukropek.
Linia 10. return False.
Linia 11. return True.
Linia 13. krawedzie znak równości otwórz nawias kwadratowy otwórz nawias kwadratowy 1 przecinek 2 zamknij nawias kwadratowy przecinek otwórz nawias kwadratowy 3 przecinek 1 zamknij nawias kwadratowy przecinek otwórz nawias kwadratowy 1 przecinek 4 zamknij nawias kwadratowy przecinek otwórz nawias kwadratowy 2 przecinek 4 zamknij nawias kwadratowy przecinek otwórz nawias kwadratowy 3 przecinek 4 zamknij nawias kwadratowy zamknij nawias kwadratowy.
Linia 14. droga1 znak równości otwórz nawias kwadratowy 1 przecinek 2 przecinek 4 przecinek 3 zamknij nawias kwadratowy.
Linia 15. droga2 znak równości otwórz nawias kwadratowy 1 przecinek 2 przecinek 3 przecinek 4 zamknij nawias kwadratowy.
Linia 16. print otwórz nawias okrągły znajdz podkreślnik droge otwórz nawias okrągły krawedzie przecinek droga1 zamknij nawias okrągły zamknij nawias okrągły.
Linia 17. print otwórz nawias okrągły znajdz podkreślnik droge otwórz nawias okrągły krawedzie przecinek droga2 zamknij nawias okrągły zamknij nawias okrągły.
def znajdz_krawedz(graf, p, q):
for i, k in enumerate(graf):
if k == [p, q] or k == [q, p]:
return i
return -1
def znajdz_droge(graf, droga):
for i, w in enumerate(droga[:-1]):
if znajdz_krawedz(graf, w, droga[i + 1]) == -1:
return False
return True
krawedzie = [[1, 2], [3, 1], [1, 4], [2, 4], [3, 4]]
droga1 = [1, 2, 4, 3]
droga2 = [1, 2, 3, 4]
print(znajdz_droge(krawedzie, droga1))
print(znajdz_droge(krawedzie, droga2))
31
Ćwiczenie 4
Uzupełnij brakujący kod metody znajdz_krawedz(wierzcholek1, wierzcholek2) w klasie Graf, która sprawdzi, czy w grafie istnieje krawędź łącząca dane wierzchołki. Działanie programu przetestuj dla podanego w kodzie grafu graf i trzech par wierzchołków wierzcholek1 i wierzcholek2:
1, 3
5, 4
2, 4
Specyfikacja problemu:
Dane:
graf – podany graf; obiekt klasy Graf
wierzcholek1, wierzcholek2 – wierzchołki grafu; liczby naturalne
Wynik:
Program wypisuje indeksy szukanych krawędzi, jeśli zostanie znaleziona krawędź łącząca dwa wierzchołki, lub -1, jeśli nie ma między nimi połączenia.
Przykładowe wyjście:
Linia 1. 1.
Linia 2. 5.
Linia 3. minus 1.
1
5
-1
R1c1DmCwNX4RV1
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.
Linia 1. class Graf dwukropek.
Linia 2. def podkreślnik podkreślnik init podkreślnik podkreślnik otwórz nawias okrągły self przecinek wierzcholki znak równości otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek krawedzie znak równości otwórz nawias kwadratowy zamknij nawias kwadratowy zamknij nawias okrągły dwukropek.
Linia 3. self kropka wierzcholki znak równości wierzcholki.
Linia 4. self kropka krawedzie znak równości krawedzie.
Linia 6. def dodaj podkreślnik wierzcholek otwórz nawias okrągły self przecinek wierzcholek zamknij nawias okrągły dwukropek.
Linia 7. if wierzcholek not in self kropka wierzcholki dwukropek.
Linia 8. self kropka wierzcholki kropka append otwórz nawias okrągły wierzcholek zamknij nawias okrągły.
Linia 10. def dodaj podkreślnik krawedz otwórz nawias okrągły self przecinek krawedz zamknij nawias okrągły dwukropek.
Linia 11. if krawedz otwórz nawias kwadratowy 0 zamknij nawias kwadratowy in self kropka wierzcholki and krawedz otwórz nawias kwadratowy 1 zamknij nawias kwadratowy in self kropka wierzcholki dwukropek.
Linia 12. self kropka krawedzie kropka append otwórz nawias okrągły krawedz zamknij nawias okrągły.
Linia 14. def znajdz podkreślnik krawedz otwórz nawias okrągły self przecinek wierzcholek1 przecinek wierzcholek2 zamknij nawias okrągły dwukropek.
Linia 15. for indeks przecinek krawedz in enumerate otwórz nawias okrągły self kropka krawedzie zamknij nawias okrągły dwukropek.
Linia 16. if krawedz znak równości znak równości otwórz nawias kwadratowy wierzcholek1 przecinek wierzcholek2 zamknij nawias kwadratowy or krawedz znak równości znak równości otwórz nawias kwadratowy wierzcholek2 przecinek wierzcholek1 zamknij nawias kwadratowy dwukropek.
Linia 17. return indeks.
Linia 18. return minus 1.
Linia 21. graf znak równości Graf otwórz nawias okrągły otwórz nawias kwadratowy 1 przecinek 2 przecinek 3 przecinek 4 przecinek 5 zamknij nawias kwadratowy przecinek otwórz nawias kwadratowy otwórz nawias kwadratowy 1 przecinek 2 zamknij nawias kwadratowy przecinek otwórz nawias kwadratowy 1 przecinek 3 zamknij nawias kwadratowy przecinek otwórz nawias kwadratowy 1 przecinek 4 zamknij nawias kwadratowy przecinek otwórz nawias kwadratowy 2 przecinek 3 zamknij nawias kwadratowy przecinek otwórz nawias kwadratowy 3 przecinek 4 zamknij nawias kwadratowy przecinek otwórz nawias kwadratowy 4 przecinek 5 zamknij nawias kwadratowy zamknij nawias kwadratowy zamknij nawias okrągły.
Linia 22. wierzcholek1 znak równości 1.
Linia 23. wierzcholek2 znak równości 3.
Linia 24. print otwórz nawias okrągły graf kropka znajdz podkreślnik krawedz otwórz nawias okrągły wierzcholek1 przecinek wierzcholek2 zamknij nawias okrągły zamknij nawias okrągły kratka 1.
Linia 25. wierzcholek1 znak równości 5.
Linia 26. wierzcholek2 znak równości 4.
Linia 27. print otwórz nawias okrągły graf kropka znajdz podkreślnik krawedz otwórz nawias okrągły wierzcholek1 przecinek wierzcholek2 zamknij nawias okrągły zamknij nawias okrągły kratka 5.
Linia 28. wierzcholek1 znak równości 2.
Linia 29. wierzcholek2 znak równości 4.
Linia 30. print otwórz nawias okrągły graf kropka znajdz podkreślnik krawedz otwórz nawias okrągły wierzcholek1 przecinek wierzcholek2 zamknij nawias okrągły zamknij nawias okrągły kratka minus 1.
class Graf:
def __init__(self, wierzcholki=[], krawedzie=[]):
self.wierzcholki = wierzcholki
self.krawedzie = krawedzie
def dodaj_wierzcholek(self, wierzcholek):
if wierzcholek not in self.wierzcholki:
self.wierzcholki.append(wierzcholek)
def dodaj_krawedz(self, krawedz):
if krawedz[0] in self.wierzcholki and krawedz[1] in self.wierzcholki:
self.krawedzie.append(krawedz)
def znajdz_krawedz(self, wierzcholek1, wierzcholek2):
for indeks, krawedz in enumerate(self.krawedzie):
if krawedz == [wierzcholek1, wierzcholek2] or krawedz == [wierzcholek2, wierzcholek1]:
return indeks
return -1
graf = Graf([1, 2, 3, 4, 5], [[1, 2], [1, 3], [1, 4], [2, 3], [3, 4], [4, 5]])
wierzcholek1 = 1
wierzcholek2 = 3
print(graf.znajdz_krawedz(wierzcholek1, wierzcholek2)) # 1
wierzcholek1 = 5
wierzcholek2 = 4
print(graf.znajdz_krawedz(wierzcholek1, wierzcholek2)) # 5
wierzcholek1 = 2
wierzcholek2 = 4
print(graf.znajdz_krawedz(wierzcholek1, wierzcholek2)) # -1
21
Ćwiczenie 5
Napisz funkcję, która wypisze listę wierzchołków grafu wraz ze wszystkimi ich sąsiadami. Działanie programu przetestuj dla następujących danych:
krawedzie – tablica krawędzi w grafie składająca się z par liczb całkowitych
wierzcholki – tablica wierzchołków w grafie; tablica liczb całkowitych
Wynik:
Program wypisuje w kolejnych wierszach indeksy wierzchołków oraz po dwukropku indeksy sąsiadów danego wierzchołka.
Przykładowe wyjście:
Linia 1. 1 dwukropek 2 3 5.
Linia 2. 2 dwukropek 1 3.
Linia 3. 3 dwukropek 1 2 4 5.
Linia 4. 4 dwukropek 3.
Linia 5. 5 dwukropek 1 3 6.
Linia 6. 6 dwukropek 5.
1: 2 3 5
2: 1 3
3: 1 2 4 5
4: 3
5: 1 3 6
6: 5
R9osLgWctaFi3
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.
Linia 1. def lista podkreślnik sasiadow otwórz nawias okrągły graf przecinek wierzcholek zamknij nawias okrągły dwukropek.
Linia 2. sasiedzi znak równości otwórz nawias kwadratowy zamknij nawias kwadratowy.
Linia 3. for krawedz in graf dwukropek.
Linia 4. if krawedz otwórz nawias kwadratowy 0 zamknij nawias kwadratowy znak równości znak równości wierzcholek dwukropek.
Linia 5. sasiedzi kropka append otwórz nawias okrągły krawedz otwórz nawias kwadratowy 1 zamknij nawias kwadratowy zamknij nawias okrągły.
Linia 7. if krawedz otwórz nawias kwadratowy 1 zamknij nawias kwadratowy znak równości znak równości wierzcholek dwukropek.
Linia 8. sasiedzi kropka append otwórz nawias okrągły krawedz otwórz nawias kwadratowy 0 zamknij nawias kwadratowy zamknij nawias okrągły.
Linia 9. sasiedzi kropka sort otwórz nawias okrągły zamknij nawias okrągły.
Linia 10. return sasiedzi.
Linia 12. def wypisz podkreślnik graf otwórz nawias okrągły graf zamknij nawias okrągły dwukropek.
Linia 13. for w in wierzcholki dwukropek.
Linia 14. sasiedzi znak równości lista podkreślnik sasiadow otwórz nawias okrągły graf przecinek w zamknij nawias okrągły.
Linia 15. lista znak równości apostrof apostrof kropka join otwórz nawias okrągły str otwórz nawias okrągły s zamknij nawias okrągły for s in sasiedzi zamknij nawias okrągły.
Linia 16. print otwórz nawias okrągły str otwórz nawias okrągły w zamknij nawias okrągły plus cudzysłów dwukropek cudzysłów plus lista zamknij nawias okrągły.
Linia 18. krawedzie znak równości otwórz nawias kwadratowy otwórz nawias kwadratowy 1 przecinek 2 zamknij nawias kwadratowy przecinek otwórz nawias kwadratowy 1 przecinek 3 zamknij nawias kwadratowy przecinek otwórz nawias kwadratowy 2 przecinek 3 zamknij nawias kwadratowy przecinek otwórz nawias kwadratowy 3 przecinek 4 zamknij nawias kwadratowy przecinek otwórz nawias kwadratowy 5 przecinek 1 zamknij nawias kwadratowy przecinek otwórz nawias kwadratowy 5 przecinek 3 zamknij nawias kwadratowy przecinek otwórz nawias kwadratowy 5 przecinek 6 zamknij nawias kwadratowy zamknij nawias kwadratowy.
Linia 19. wierzcholki znak równości otwórz nawias kwadratowy 1 przecinek 2 przecinek 3 przecinek 4 przecinek 5 przecinek 6 zamknij nawias kwadratowy.
Linia 20. wypisz podkreślnik graf otwórz nawias okrągły krawedzie zamknij nawias okrągły.
def lista_sasiadow(graf, wierzcholek):
sasiedzi = []
for krawedz in graf:
if krawedz[0] == wierzcholek:
sasiedzi.append(krawedz[1])
if krawedz[1] == wierzcholek:
sasiedzi.append(krawedz[0])
sasiedzi.sort()
return sasiedzi
def wypisz_graf(graf):
for w in wierzcholki:
sasiedzi = lista_sasiadow(graf, w)
lista = ' '.join(str(s) for s in sasiedzi)
print(str(w) + ": " + lista)
krawedzie = [[1, 2], [1, 3], [2, 3], [3, 4], [5, 1], [5, 3], [5, 6]]
wierzcholki = [1, 2, 3, 4, 5, 6]
wypisz_graf(krawedzie)
21
Ćwiczenie 6
Zmodyfikuj funkcję wypisz_graf tak, aby program wypisywał stopnie kolejnych wierzchołków (stopień wierzchołka jest równy liczbie wszystkich krawędzi, dla których dany wierzchołek jest końcem lub początkiem). Graf reprezentowany jest przez listę krawędzi. Każdy wierzchołek może pojawić się tylko raz. Działanie programu przetestuj dla następujących danych:
krawedzie – tablica krawędzi w grafie składająca się z par liczb całkowitych
wierzcholki – tablica wierzchołków w grafie; tablica liczb całkowitych
Wynik:
Program wypisuje stopnie kolejnych wierzchołków.
Przykładowe wyjście:
Linia 1. 0 dwukropek 1.
Linia 2. 1 dwukropek 3.
Linia 3. 2 dwukropek 2.
Linia 4. 3 dwukropek 3.
Linia 5. 4 dwukropek 1.
Linia 6. 5 dwukropek 3.
Linia 7. 6 dwukropek 3.
0 : 1
1 : 3
2 : 2
3 : 3
4 : 1
5 : 3
6 : 3
R1e5SCm3OLYCR
Wymyśl pytanie na kartkówkę związane z tematem materiału.
Wymyśl pytanie na kartkówkę związane z tematem materiału.
Linia 1. def lista podkreślnik sasiadow otwórz nawias okrągły graf przecinek wierzcholek zamknij nawias okrągły dwukropek.
Linia 2. sasiedzi znak równości otwórz nawias kwadratowy zamknij nawias kwadratowy.
Linia 3. for krawedz in graf dwukropek.
Linia 4. if krawedz otwórz nawias kwadratowy 0 zamknij nawias kwadratowy znak równości znak równości wierzcholek dwukropek.
Linia 5. sasiedzi kropka append otwórz nawias okrągły krawedz otwórz nawias kwadratowy 1 zamknij nawias kwadratowy zamknij nawias okrągły.
Linia 7. if krawedz otwórz nawias kwadratowy 1 zamknij nawias kwadratowy znak równości znak równości wierzcholek dwukropek.
Linia 8. sasiedzi kropka append otwórz nawias okrągły krawedz otwórz nawias kwadratowy 0 zamknij nawias kwadratowy zamknij nawias okrągły.
Linia 9. sasiedzi kropka sort otwórz nawias okrągły zamknij nawias okrągły.
Linia 10. return sasiedzi.
Linia 12. def wypisz podkreślnik graf otwórz nawias okrągły graf zamknij nawias okrągły dwukropek.
Linia 13. for w in wierzcholki dwukropek.
Linia 14. sasiedzi znak równości lista podkreślnik sasiadow otwórz nawias okrągły graf przecinek w zamknij nawias okrągły.
Linia 15. stopien znak równości len otwórz nawias okrągły sasiedzi zamknij nawias okrągły.
Linia 16. lista znak równości apostrof apostrof kropka join otwórz nawias okrągły str otwórz nawias okrągły s zamknij nawias okrągły for s in sasiedzi zamknij nawias okrągły.
Linia 17. print otwórz nawias okrągły str otwórz nawias okrągły w zamknij nawias okrągły przecinek cudzysłów dwukropek cudzysłów przecinek stopien zamknij nawias okrągły.
Linia 19. krawedzie znak równości otwórz nawias kwadratowy otwórz nawias kwadratowy 0 przecinek 6 zamknij nawias kwadratowy przecinek otwórz nawias kwadratowy 1 przecinek 2 zamknij nawias kwadratowy przecinek otwórz nawias kwadratowy 1 przecinek 3 zamknij nawias kwadratowy przecinek otwórz nawias kwadratowy 2 przecinek 6 zamknij nawias kwadratowy przecinek otwórz nawias kwadratowy 3 przecinek 4 zamknij nawias kwadratowy przecinek otwórz nawias kwadratowy 5 przecinek 1 zamknij nawias kwadratowy przecinek otwórz nawias kwadratowy 5 przecinek 3 zamknij nawias kwadratowy przecinek otwórz nawias kwadratowy 5 przecinek 6 zamknij nawias kwadratowy zamknij nawias kwadratowy.
Linia 20. wierzcholki znak równości otwórz nawias kwadratowy 0 przecinek 1 przecinek 2 przecinek 3 przecinek 4 przecinek 5 przecinek 6 zamknij nawias kwadratowy.
Linia 21. wypisz podkreślnik graf otwórz nawias okrągły krawedzie zamknij nawias okrągły.
def lista_sasiadow(graf, wierzcholek):
sasiedzi = []
for krawedz in graf:
if krawedz[0] == wierzcholek:
sasiedzi.append(krawedz[1])
if krawedz[1] == wierzcholek:
sasiedzi.append(krawedz[0])
sasiedzi.sort()
return sasiedzi
def wypisz_graf(graf):
for w in wierzcholki:
sasiedzi = lista_sasiadow(graf, w)
stopien = len(sasiedzi)
lista = ' '.join(str(s) for s in sasiedzi)
print(str(w),":",stopien)
krawedzie = [[0, 6], [1, 2], [1, 3], [2, 6], [3, 4], [5, 1], [5, 3], [5, 6]]
wierzcholki = [0, 1, 2, 3, 4, 5, 6]
wypisz_graf(krawedzie)