Grafy a jejich implementace - Historie editací

Acolade: kategorizace

2014-02-20T06:35:27Z

kategorizace

← Starší verze		Verze z 20. 2. 2014, 06:35
Řádka 33:		Řádka 33:

	{{fav-kiv-bzinf}}		{{fav-kiv-bzinf}}
		+	[[Kategorie:fav-kiv-bzinf]]

Tester: /* Implementace grafu pomocí spojového seznamu (seznam sousednosti) */

2011-08-26T08:22:11Z

Implementace grafu pomocí spojového seznamu (seznam sousednosti)

← Starší verze		Verze z 26. 8. 2011, 08:22
Řádka 11:		Řádka 11:
	== Implementace grafu pomocí spojového seznamu (seznam sousednosti) ==		== Implementace grafu pomocí spojového seznamu (seznam sousednosti) ==

−	[[Soubor:Graf-spojovy-seznam.jpg]]	+	[[Soubor:Graf-spojovy-seznam.jpg\|500px]]

	Máme seznam vrcholů a pro každý z nich máme seznam vrcholů, se kterými sousedí. Lze tak implementovat všechny 3 typy grafů (v obousměrných budou sousednosti v seznamech obou vrcholů sdílejících hranu, ohodnocení vrcholů je uloženo v seznamu vrcholů, ohodnocení hran je v seznamu sousednosti)		Máme seznam vrcholů a pro každý z nich máme seznam vrcholů, se kterými sousedí. Lze tak implementovat všechny 3 typy grafů (v obousměrných budou sousednosti v seznamech obou vrcholů sdílejících hranu, ohodnocení vrcholů je uloženo v seznamu vrcholů, ohodnocení hran je v seznamu sousednosti)

	Problém metody je v složitosti hledání existence hrany, jelikož musíme procházet seznamy sousednost (Pro velké grafy pomalé, na druhou stranu pro řídké grafy méně pamětově náročné)		Problém metody je v složitosti hledání existence hrany, jelikož musíme procházet seznamy sousednost (Pro velké grafy pomalé, na druhou stranu pro řídké grafy méně pamětově náročné)
−
−

	== Implementace grafu pomocí matice sousednosti ==		== Implementace grafu pomocí matice sousednosti ==

Tester v 23. 8. 2011, 23:38

2011-08-23T23:38:22Z

← Starší verze		Verze z 23. 8. 2011, 23:38
Řádka 33:		Řádka 33:

	// co třeba hledání kostry grafu a podobný vylomeniny?		// co třeba hledání kostry grafu a podobný vylomeniny?
		+
		+	{{fav-kiv-bzinf}}

Tester: /* Implementace grafu pomocí matice sousednosti */

2011-08-09T06:17:14Z

Implementace grafu pomocí matice sousednosti

← Starší verze		Verze z 9. 8. 2011, 06:17
Řádka 32:		Řádka 32:


−	// co třeba ~~hlefání~~ kostry grafu a podobný vylomeniny?	+	// co třeba hledání kostry grafu a podobný vylomeniny?

Tester: /* Implementace grafu pomocí matice sousednosti */

2011-08-09T06:16:34Z

Implementace grafu pomocí matice sousednosti

← Starší verze		Verze z 9. 8. 2011, 06:16
Řádka 20:		Řádka 20:

	== Implementace grafu pomocí matice sousednosti ==		== Implementace grafu pomocí matice sousednosti ==
−
−	~~[[Soubor:Graf-seznam-sousednosti.jpg]]~~

	Stejný graf jako v předchozím případě		Stejný graf jako v předchozím případě
		+
		+	[[Soubor:Graf-seznam-sousednosti.jpg]]

	Vytvoříme matici v*v prvků, kde v je počet vrcholů a hrany reprezentujeme jedničkami, zbytek matice jsou nuly.		Vytvoříme matici v*v prvků, kde v je počet vrcholů a hrany reprezentujeme jedničkami, zbytek matice jsou nuly.

Tester: /* Implementace grafu pomocí matice sousednosti */

2011-08-09T06:14:37Z

Implementace grafu pomocí matice sousednosti

← Starší verze		Verze z 9. 8. 2011, 06:14
Řádka 21:		Řádka 21:
	== Implementace grafu pomocí matice sousednosti ==		== Implementace grafu pomocí matice sousednosti ==

−		+	[[Soubor:Graf-seznam-sousednosti.jpg]]

	Stejný graf jako v předchozím případě		Stejný graf jako v předchozím případě

Tester v 9. 8. 2011, 06:13

2011-08-09T06:13:22Z

← Starší verze		Verze z 9. 8. 2011, 06:13
Řádka 10:		Řádka 10:

	== Implementace grafu pomocí spojového seznamu (seznam sousednosti) ==		== Implementace grafu pomocí spojového seznamu (seznam sousednosti) ==
		+
		+	[[Soubor:Graf-spojovy-seznam.jpg]]

	Máme seznam vrcholů a pro každý z nich máme seznam vrcholů, se kterými sousedí. Lze tak implementovat všechny 3 typy grafů (v obousměrných budou sousednosti v seznamech obou vrcholů sdílejících hranu, ohodnocení vrcholů je uloženo v seznamu vrcholů, ohodnocení hran je v seznamu sousednosti)		Máme seznam vrcholů a pro každý z nich máme seznam vrcholů, se kterými sousedí. Lze tak implementovat všechny 3 typy grafů (v obousměrných budou sousednosti v seznamech obou vrcholů sdílejících hranu, ohodnocení vrcholů je uloženo v seznamu vrcholů, ohodnocení hran je v seznamu sousednosti)

Tester: /* Implementace grafu pomocí matice sousednosti */

2011-08-09T06:07:16Z

Implementace grafu pomocí matice sousednosti

← Starší verze		Verze z 9. 8. 2011, 06:07
Řádka 28:		Řádka 28:

	Ohodnocení lze provést uložením hodnoty místo jedniček, na diagonále lze ohodnotit vrcholy.		Ohodnocení lze provést uložením hodnoty místo jedniček, na diagonále lze ohodnotit vrcholy.
		+
		+
		+	// co třeba hlefání kostry grafu a podobný vylomeniny?

Tester v 8. 8. 2011, 16:25

2011-08-08T16:25:36Z

← Starší verze		Verze z 8. 8. 2011, 16:25
Řádka 1:		Řádka 1:
	Graf je reprezentován množinou vrcholů (uzlů) V, které mohou být spojeny určitým počtem hran H. Graf je poté definován jako G(V,H)		Graf je reprezentován množinou vrcholů (uzlů) V, které mohou být spojeny určitým počtem hran H. Graf je poté definován jako G(V,H)

−	* '''Neorientovaný graf''': Hrany grafu nejsou orientované, tedy pokud vede hrana z ~~uzli~~ 1 do uzlu 5, vede i z uzlu 5 do uzlu 1 a platí tedy (u1, u2) = (u2, u1)	+	* '''Neorientovaný graf''': Hrany grafu nejsou orientované, tedy pokud vede hrana z uzlu 1 do uzlu 5, vede i z uzlu 5 do uzlu 1 a platí tedy (u1, u2) = (u2, u1)
−	* '''Orientovaný graf''': Hrany grafu jsou orientované (jednosměrné), tedy pokud vede hrana z ~~uzli~~ 1 do uzlu 5, nevede z uzlu 5 do uzlu 1 a platí tedy (u1, u2) != (u2, u1)	+	* '''Orientovaný graf''': Hrany grafu jsou orientované (jednosměrné), tedy pokud vede hrana z uzlu 1 do uzlu 5, nevede automaticky zpět z uzlu 5 do uzlu 1 a platí tedy (u1, u2) != (u2, u1)
−	* '''Ohodnocený graf''': ~~Vednotlivé vrcholy či~~ hrany ~~mohou být ohodnoceny~~, graf ~~tedy poté lze převést na množinu reálných čísel G~~(~~V, H~~) ~~-> R~~	+
		+
		+	* '''Ohodnocený graf''': Každá hrana má přižezenou svoji hodnotu (číslo). Tyto hodnoty pak udávají například délku hrany, propustnost nebo třeba cenu za přechod po dané hraně.
		+	* '''Neohodnocený graf''': Všechhny hrany grafu jsou si rovny (v podstatě jsou všechny ohodnoceny stejným číslem), takže nemá smysl uchocácat informaci o jejich ohodnocení.

81.201.60.162 v 8. 8. 2011, 16:09

2011-08-08T16:09:58Z

← Starší verze		Verze z 8. 8. 2011, 16:09
Řádka 1:		Řádka 1:
−	~~Grafy:~~
−
	Graf je reprezentován množinou vrcholů (uzlů) V, které mohou být spojeny určitým počtem hran H. Graf je poté definován jako G(V,H)		Graf je reprezentován množinou vrcholů (uzlů) V, které mohou být spojeny určitým počtem hran H. Graf je poté definován jako G(V,H)

−	Neorientovaný graf: Hrany grafu nejsou orientované, tedy pokud vede hrana z uzli 1 do uzlu 5, vede i z uzlu 5 do uzlu 1 a platí tedy (u1, u2) = (u2, u1)	+	* '''Neorientovaný graf''': Hrany grafu nejsou orientované, tedy pokud vede hrana z uzli 1 do uzlu 5, vede i z uzlu 5 do uzlu 1 a platí tedy (u1, u2) = (u2, u1)
−	Orientovaný graf: Hrany grafu jsou orientované (jednosměrné), tedy pokud vede hrana z uzli 1 do uzlu 5, nevede z uzlu 5 do uzlu 1 a platí tedy (u1, u2) != (u2, u1)	+	* '''Orientovaný graf''': Hrany grafu jsou orientované (jednosměrné), tedy pokud vede hrana z uzli 1 do uzlu 5, nevede z uzlu 5 do uzlu 1 a platí tedy (u1, u2) != (u2, u1)
−	Ohodnocený graf: Vednotlivé vrcholy či hrany mohou být ohodnoceny, graf tedy poté lze převést na množinu reálných čísel G(V, H) -> R	+	* '''Ohodnocený graf''': Vednotlivé vrcholy či hrany mohou být ohodnoceny, graf tedy poté lze převést na množinu reálných čísel G(V, H) -> R

−	~~Implementace grafu:~~

−	~~1) Spojovými seznamy -~~ seznam sousednosti	+	== Implementace grafu pomocí spojového seznamu (seznam sousednosti) ==
−		+
−		+

	Máme seznam vrcholů a pro každý z nich máme seznam vrcholů, se kterými sousedí. Lze tak implementovat všechny 3 typy grafů (v obousměrných budou sousednosti v seznamech obou vrcholů sdílejících hranu, ohodnocení vrcholů je uloženo v seznamu vrcholů, ohodnocení hran je v seznamu sousednosti)		Máme seznam vrcholů a pro každý z nich máme seznam vrcholů, se kterými sousedí. Lze tak implementovat všechny 3 typy grafů (v obousměrných budou sousednosti v seznamech obou vrcholů sdílejících hranu, ohodnocení vrcholů je uloženo v seznamu vrcholů, ohodnocení hran je v seznamu sousednosti)
Řádka 17:		Řádka 12:
	Problém metody je v složitosti hledání existence hrany, jelikož musíme procházet seznamy sousednost (Pro velké grafy pomalé, na druhou stranu pro řídké grafy méně pamětově náročné)		Problém metody je v složitosti hledání existence hrany, jelikož musíme procházet seznamy sousednost (Pro velké grafy pomalé, na druhou stranu pro řídké grafy méně pamětově náročné)

−	~~2) Maticí~~ sousednosti	+
		+
		+	== Implementace grafu pomocí matice sousednosti ==



−	Stejný graf jako v 1)	+	Stejný graf jako v předchozím případě

	Vytvoříme matici v*v prvků, kde v je počet vrcholů a hrany reprezentujeme jedničkami, zbytek matice jsou nuly.		Vytvoříme matici v*v prvků, kde v je počet vrcholů a hrany reprezentujeme jedničkami, zbytek matice jsou nuly.