https://wiki-de.moshellshocker.dns64.de/index.php?action=history&feed=atom&title=Kritischer_GraphKritischer Graph - Versionsgeschichte2026-05-27T08:30:56ZVersionsgeschichte dieser Seite in Wikipedia (Deutsch) – Lokale KopieMediaWiki 1.43.8https://wiki-de.moshellshocker.dns64.de/index.php?title=Kritischer_Graph&diff=1772449&oldid=previmported>Kmhkmh: entspricht nicht der angebenen Definition und Literaturquelle2025-03-18T12:57:50Z<p>entspricht nicht der angebenen Definition und Literaturquelle</p>
<p><b>Neue Seite</b></p><div>[[Datei:4-critical_graph.png|mini|Ein Beispiel für einen 4-kritischen Graphen. Seine chromatische Zahl ist 4, aber alle seine richtigen Untergraphen haben eine chromatische Zahl kleiner als 4.]]<br />
Ein '''kritischer Graph''' ist ein Begriff aus der [[Graphentheorie]], der 1965 vom [[Vadim G. Vizing]] zur Untersuchung von [[Kantenfärbung]]en eingeführt worden ist. Er beschreibt eine Sorte von Graphen, deren [[chromatischer Index]] sich durch das Entfernen einer beliebigen Kante immer verkleinert.<br />
<br />
== Definition ==<br />
Ein schlichter zusammenhängender [[Klassifizierung (Graphentheorie)|Klasse 2-Graph]] ''G'' heißt '''kritisch''', falls für jede Kante <math> k\in K(G) </math> gilt:<br />
:<math>\chi^{\prime}(G-k) < \chi^{\prime}(G) </math><br />
<br />
Hierbei bezeichnet <math>\chi^{\prime}</math> den chromatischen Index eines Graphen und ein Klasse 2-Graph einen Graphen, dessen chromatischer Index größer ist als sein Maximalgrad ( <math> \chi^{\prime}(G) > \Delta(G)</math> ).<br />
<br />
== Literatur ==<br />
* Lutz Volkmann: ''Fundamente der Graphentheorie'', Springer (Wien) 1996, ISBN 3-211-82774-9, S. 292ff<br />
<br />
== Weblinks ==<br />
{{commonscat|critical graph}}<br />
* Lutz Volkmann: ''[https://www.math2.rwth-aachen.de/files/gt/buch/graphen_an_allen_ecken_und_kanten.pdf Graphen an allen Ecken und Kanten] (PDF; 3,5&nbsp;MB)'', Skript 2006, S. 244ff<br />
<br />
[[Kategorie:Graphentheorie]]<br />
[[Kategorie:Graph]]</div>imported>Kmhkmh