Stromový rozklad - Historie editací

Sysop: Nahrazení textu „“ textem „\)“

2022-08-14T14:53:46Z

Nahrazení textu „</math>“ textem „\)</big>“

← Starší verze		Verze z 14. 8. 2022, 14:53
Řádka 19:		Řádka 19:
	== Stromová šířka ==		== Stromová šířka ==

-	'''Stromová šířka''' grafu tw(G) se definuje jako <big>\(\min_T \max_{X \in V(T)}\|X\|-1</~~math~~>, tedy nejmenší možná šířka rozkladu přes všechny rozklady.	+	'''Stromová šířka''' grafu tw(G) se definuje jako <big>$\min_T \max_{X \in V(T)}\|X\|-1$</big>, tedy nejmenší možná šířka rozkladu přes všechny rozklady.

	== Třídy grafů omezené stromové šířky ==		== Třídy grafů omezené stromové šířky ==

Sysop: Nahrazení textu „ $“ textem „$ \(“

2022-08-14T14:50:10Z

Nahrazení textu „<math>“ textem „<big>\(“

← Starší verze		Verze z 14. 8. 2022, 14:50
Řádka 19:		Řádka 19:
	== Stromová šířka ==		== Stromová šířka ==

-	'''Stromová šířka''' grafu tw(G) se definuje jako <~~math~~>\min_T \max_{X \in V(T)}\|X\|-1</math>, tedy nejmenší možná šířka rozkladu přes všechny rozklady.	+	'''Stromová šířka''' grafu tw(G) se definuje jako <big>\(\min_T \max_{X \in V(T)}\|X\|-1</math>, tedy nejmenší možná šířka rozkladu přes všechny rozklady.

	== Třídy grafů omezené stromové šířky ==		== Třídy grafů omezené stromové šířky ==

Sysop: + Nový článek

2015-10-08T09:26:41Z

+ Nový článek

← Starší verze		Verze z 8. 10. 2015, 09:26
Řádka 1:		Řádka 1:
-	~~{{Wikipedia-cs~~\|~~Stromový rozklad~~\|~~700}}~~	+	[[Soubor:Tree decomposition.png\|thumb\|230px\|Graf na osmi vrcholech a jeho stromový rozklad. Každý vrchol musí mít ve stromě souvislý výskyt a každá hrana musí být obsažena v některém uzlu. Šířka tohoto rozkladu je 2, protože největší uzel má velikost 3.]]

		+	'''Stromový rozklad''' je jeden ze způsobů, jak charakterizovat [[Graf (teorie grafů)\|graf]].
		+
		+	== Definice ==
		+
		+	[[Strom (teorie grafů)\|Strom]] T je stromový rozklad grafu G, pokud jeho vrcholy jsou tvořeny podmnožinami V(G) a platí:
		+	# žádný X z V(T) není prázdný a každý ''v'' z V(G) je v nějakém X
		+	# pro každou hranu {v,w} grafu G existuje X z V(T) takové, že {v,w} je podmnožinou X
		+	# vrcholy rozkladu T obsahující libovolný vrchol ''v'' grafu G [[Podgraf#Indukovaný podgraf\|indukují]] souvislý podstrom (''v'' má v T souvislý výskyt)
		+
		+	Vrcholům stromového rozkladu se říká ''uzly'', aby se odlišily od vrcholů původního grafu.
		+
		+	Pro každý graf existuje stromový rozklad, například triviální rozklad, který jedinému uzlu přiřadí všechny vrcholy.
		+
		+	== Šířka rozkladu ==
		+	'''Šířka rozkladu''' je velikost největšího uzlu bez jedné.
		+
		+	== Stromová šířka ==
		+
		+	'''Stromová šířka''' grafu tw(G) se definuje jako <math>\min_T \max_{X \in V(T)}\|X\|-1</math>, tedy nejmenší možná šířka rozkladu přes všechny rozklady.
		+
		+	== Třídy grafů omezené stromové šířky ==
		+	# grafy stromové šířky 0 jsou pouze grafy bez hran, hrana vynutí uzel velikosti alespoň 2
		+	# grafy stromové šířky nejvýše 1 jsou lesy, každý les má rozklad takový, že uzly odpovídají hranám
		+	# grafy stromové šířky nejvýše 2 jsou [[sériově paralelní graf]]y
		+
		+	Třídy grafů omezené stromové šířky jsou uzavřené na [[Minor (teorie grafů)\|minory]], žádné [[Minor (teorie grafů)#Minorové operace\|minorové operace]] nezvyšují stromovou šířku. Odebrání vrcholu se v rozkladu projeví odebráním vrcholu ze všech uzlů, odebrání hrany se neprojeví vůbec, kontrakce nahrazením jednoho vrcholu jeho sousedem přes kontrahovanou hranu a odstraněním duplicit.
		+
		+	== Chordální grafy ==
		+	: ''Související informace naleznete také v článku'': [[Chordální graf]].
		+
		+	''Chordální graf'' je takový, který neobsahuje cyklus délky alespoň 4 jako [[Podgraf#Indukovaný podgraf\|indukovaný podgraf]] (každý takový cyklus má chordu — hranu spojující vrcholy, které nejsou na cyklu za sebou). Tyto grafy jsou specifické tím, že pro ně existuje stromový rozklad takový, že každý uzel indukuje [[Klika (teorie grafů)\|kliku]], ten je navíc snadné zkonstruovat. Platí, že pro každý graf je stromová šířka rovna nejmenší klikovosti přes všechny chordální nadgrafy bez jedné.
		+
		+
		+	{{Článek z Wikipedie}}
	[[Kategorie:Grafové pojmy]]		[[Kategorie:Grafové pojmy]]

Sysop: 1 revizi

2013-11-11T08:18:26Z

1 revizi

← Starší verze

Verze z 11. 11. 2013, 08:18

Sysop: + Nový článek

2012-10-22T01:17:57Z

+ Nový článek

Nová stránka

{{Wikipedia-cs|Stromový rozklad|700}}

[[Kategorie:Grafové pojmy]]

Stromový rozklad - Historie editací

Sysop: Nahrazení textu „“ textem „\)“

Sysop: Nahrazení textu „“ textem „\(“

Sysop: + Nový článek

Sysop: 1 revizi

Sysop: + Nový článek

Sysop: Nahrazení textu „ $“ textem „$ \(“