Sprawdź się

Pokaż ćwiczenia:

RQK2jK1N4AxSi1

Ćwiczenie 1

Uzupełnij tabelę będącą macierzą incydencji grafu, którego macierz sąsiedztwa ma następującą postać:

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

RUOLAduVb8z4I

RKaxxqCU867J71

Ćwiczenie 2

Uzupełnij tabelę będącą macierzą sąsiedztwa grafu, którego macierz incydencji ma następującą postać:

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

R1DqTpmPxBAkV

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.

| E |

par dwóch elementów, 3.

| V | \times | V |

, 4.

| V | \times | E |

Lista sąsiedztwa Możliwe odpowiedzi: 1. zależy od stopnia każdego wierzchołka, 2.

| E |

par dwóch elementów, 3.

| V | \times | V |

, 4.

| V | \times | E |

Macierz incydencji Możliwe odpowiedzi: 1. zależy od stopnia każdego wierzchołka, 2.

| E |

par dwóch elementów, 3.

| V | \times | V |

, 4.

| V | \times | E |

Lista krawędzi Możliwe odpowiedzi: 1. zależy od stopnia każdego wierzchołka, 2.

| E |

par dwóch elementów, 3.

| V | \times | V |

, 4.

| V | \times | E |

R1ETVen1b1ATY1

Ćwiczenie 4

Połącz w pary reprezentacje z odpowiednią strukturą danych. Lista sąsiedztwa Możliwe odpowiedzi: 1. int[V][V], 2. std::vector[E], 3. int[V][E] Macierz sąsiedztwa Możliwe odpowiedzi: 1. int[V][V], 2. std::vector[E], 3. int[V][E] Macierz incydencji Możliwe odpowiedzi: 1. int[V][V], 2. std::vector[E], 3. int[V][E]

R19ifdFR3Ztz021

Ćwiczenie 5

R1ANMnAUVvngZ21

Ćwiczenie 6

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

R13IwlG5Aj9Uq21

Ćwiczenie 7

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

Ćwiczenie 8

Dany jest graf nieskierowany bez wag. Napisz funkcję, która przekształci macierz sąsiedztwa w listę sąsiedztwa.

RtiAjiacZs0JT

Przykładowe rozwiązanie zadania:

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 2. kratka include otwórz nawias ostrokątny vector zamknij nawias ostrokątny. Linia 3. kratka define n 5. Linia 5. using namespace std średnik. Linia 7. vector otwórz nawias ostrokątny int zamknij nawias ostrokątny listaSasiedztwa otwórz nawias kwadratowy n zamknij nawias kwadratowy średnik. Linia 9. int macierzSasiedztwa otwórz nawias kwadratowy n zamknij nawias kwadratowy otwórz nawias kwadratowy n zamknij nawias kwadratowy znak równości otwórz nawias klamrowy. Linia 10. otwórz nawias klamrowy 0 przecinek 1 przecinek 1 przecinek 1 przecinek 1 zamknij nawias klamrowy przecinek. Linia 11. otwórz nawias klamrowy 1 przecinek 0 przecinek 1 przecinek 1 przecinek 1 zamknij nawias klamrowy przecinek. Linia 12. otwórz nawias klamrowy 1 przecinek 1 przecinek 0 przecinek 0 przecinek 1 zamknij nawias klamrowy przecinek. Linia 13. otwórz nawias klamrowy 1 przecinek 1 przecinek 0 przecinek 0 przecinek 1 zamknij nawias klamrowy przecinek. Linia 14. otwórz nawias klamrowy 1 przecinek 1 przecinek 1 przecinek 1 przecinek 0 zamknij nawias klamrowy. Linia 15. zamknij nawias klamrowy średnik. Linia 17. void przeksztalc otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 18. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 19. for otwórz nawias okrągły int j znak równości 0 średnik j otwórz nawias ostrokątny n średnik j plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. if otwórz nawias okrągły macierzSasiedztwa otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy j zamknij nawias kwadratowy zamknij nawias okrągły. Linia 21. listaSasiedztwa otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka push podkreślnik back otwórz nawias okrągły j zamknij nawias okrągły średnik. Linia 22. zamknij nawias klamrowy. Linia 23. zamknij nawias klamrowy. Linia 24. zamknij nawias klamrowy. Linia 26. void wypisz otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 28. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 29. przeksztalc otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 30. wypisz otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 32. return 0 średnik. Linia 33. zamknij nawias klamrowy. Linia 35. void wypisz otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 36. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 37. cout otwórz nawias ostrokątny otwórz nawias ostrokątny i otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów dwukropek cudzysłów średnik. Linia 39. for otwórz nawias okrągły int sasiad dwukropek listaSasiedztwa otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły. Linia 40. cout otwórz nawias ostrokątny otwórz nawias ostrokątny sasiad otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów cudzysłów średnik. Linia 42. cout otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 43. zamknij nawias klamrowy. Linia 44. zamknij nawias klamrowy.

#include <iostream>
#include <vector>
#define n 5

using namespace std;

vector<int> listaSasiedztwa[n];

int macierzSasiedztwa[n][n] = {
	{ 0, 1, 1, 1, 1 },
	{ 1, 0, 1, 1, 1 },
	{ 1, 1, 0, 0, 1 },
	{ 1, 1, 0, 0, 1 },
	{ 1, 1, 1, 1, 0 }
};

void przeksztalc() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (macierzSasiedztwa[i][j])
				listaSasiedztwa[i].push_back(j);
		}
	}
}

void wypisz();

int main() {
	przeksztalc();
	wypisz();

	return 0;
}

void wypisz() {
	for (int i = 0; i < n; i++) {
		cout << i << ": ";

		for (int sasiad : listaSasiedztwa[i])
			cout << sasiad << " ";

		cout << endl;
	}
}

Ćwiczenie 9

Dany jest graf nieskierowany bez wag. Napisz funkcję, która przekształci listę sąsiedztwa w macierz incydencji.

R1U8NBrwjZKv1

Przykładowe rozwiązanie zadania:

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 2. kratka include otwórz nawias ostrokątny vector zamknij nawias ostrokątny. Linia 3. kratka define n 5. Linia 4. kratka define E 10. Linia 6. using namespace std średnik. Linia 8. vector otwórz nawias ostrokątny int zamknij nawias ostrokątny listaSasiedztwa otwórz nawias kwadratowy n zamknij nawias kwadratowy znak równości otwórz nawias klamrowy. Linia 9. otwórz nawias klamrowy 1 przecinek 2 przecinek 3 przecinek 4 zamknij nawias klamrowy przecinek. Linia 10. otwórz nawias klamrowy 0 przecinek 2 przecinek 3 przecinek 4 zamknij nawias klamrowy przecinek. Linia 11. otwórz nawias klamrowy 0 przecinek 1 przecinek 4 zamknij nawias klamrowy przecinek. Linia 12. otwórz nawias klamrowy 0 przecinek 1 przecinek 4 zamknij nawias klamrowy przecinek. Linia 13. otwórz nawias klamrowy 0 przecinek 1 przecinek 2 przecinek 3 zamknij nawias klamrowy. Linia 14. zamknij nawias klamrowy średnik. Linia 16. int macierzIncydencji otwórz nawias kwadratowy n zamknij nawias kwadratowy otwórz nawias kwadratowy E zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 0 zamknij nawias klamrowy średnik. Linia 18. int m znak równości 0 średnik. Linia 20. void przeksztalc otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 21. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 22. for otwórz nawias okrągły int j dwukropek listaSasiedztwa otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 23. if otwórz nawias okrągły i zamknij nawias ostrokątny j zamknij nawias okrągły continue średnik. Linia 25. macierzIncydencji otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy m zamknij nawias kwadratowy znak równości 1 średnik. Linia 26. macierzIncydencji otwórz nawias kwadratowy j zamknij nawias kwadratowy otwórz nawias kwadratowy m zamknij nawias kwadratowy znak równości 1 średnik. Linia 27. m plus plus średnik. Linia 28. zamknij nawias klamrowy. Linia 29. zamknij nawias klamrowy. Linia 30. zamknij nawias klamrowy. Linia 32. void wypisz otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 34. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 35. przeksztalc otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 36. wypisz otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 38. return 0 średnik. Linia 39. zamknij nawias klamrowy. Linia 41. void wypisz otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 42. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 43. for otwórz nawias okrągły int j znak równości 0 średnik j otwórz nawias ostrokątny m średnik j plus plus zamknij nawias okrągły. Linia 44. cout otwórz nawias ostrokątny otwórz nawias ostrokątny macierzIncydencji otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy j zamknij nawias kwadratowy otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów cudzysłów średnik. Linia 46. cout otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 47. zamknij nawias klamrowy. Linia 48. zamknij nawias klamrowy.

#include <iostream>
#include <vector>
#define n 5
#define E 10

using namespace std;

vector<int> listaSasiedztwa[n] = {
	{1, 2, 3, 4},
	{0, 2, 3, 4},
	{0, 1, 4},
	{0, 1, 4},
	{0, 1, 2, 3}
};

int macierzIncydencji[n][E] = { 0 };

int m = 0;

void przeksztalc() {
	for (int i = 0; i < n; i++) {
		for (int j : listaSasiedztwa[i]) {
			if (i > j) continue;

			macierzIncydencji[i][m] = 1;
			macierzIncydencji[j][m] = 1;
			m++;
		}
	}
}

void wypisz();

int main() {
	przeksztalc();
	wypisz();

	return 0;
}

void wypisz() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			cout << macierzIncydencji[i][j] << " ";

		cout << endl;
	}
}

Prezentacja multimedialna

Dla nauczyciela