Klassifizierung (Graphentheorie)
- Klassifizierung (Graphentheorie)
-
Als Klassifizierung oder auch Klassifizierungsproblem bezeichnet man in der Graphentheorie die Zuordnung von Graphen zu einer der beiden wie folgt definierten Klassen:
- Klasse 1: Ein Multigraph G dessen Maximalgrad seinen chromatischen Index entspricht, d.h.
.
- Klasse 2: Ein Multigraph G dessen chromatischer Index größer ist als sein Maximalgrad ist, d.h.
.
Entsprechend seiner Zuordnung wird dann ein Graph dann auch als Klasse 1-Graph oder einen Klasse 2-Graph bezeichnet.
Literatur
- Lutz Volkmann: Fundamente der Graphentheorie, Springer (Wien) 1996, ISBN 3-211-82774-9, S. 289, 299ff
Weblinks
Wikimedia Foundation.
Schlagen Sie auch in anderen Wörterbüchern nach:
Kante (Graphentheorie) — Eine Kante (manchmal auch Bogen genannt) ist in der Graphentheorie ein Teil eines Graphen, der zwei Knoten (vernetzte Punkte) miteinander verbindet. Die Art der Kanten (gerichtet oder ungerichtet) ist ein wichtiges Merkmal zur Klassifizierung von … Deutsch Wikipedia
Polyhierarchie — Polyhierarchische Relationen Polyhierarchie bezeichnet im Zusammenhang mit Begriffssystemen wie Ontologien und Thesauri (Begriffshierarchien) eine hierarchische Struktur, in der eine Klasse mehr als eine übergeordnete Klasse haben kann. Somit… … Deutsch Wikipedia
Generation language — Quelltext eines Programms in der objektorientierten Programmiersprache Ruby. Eine Programmiersprache ist eine Notation für Computerprogramme; sie dient sowohl dazu, diese während und nach ihrer Entwicklung (Programmierung) darzustellen als auch… … Deutsch Wikipedia
Hierarchisch — Als Hierarchie ([hirarˈçiː] oder [hi̯erarˈçiː]) (griechisch ιεραρχία, ein Kompositum aus ιερή, hieré heilige und αρχή, arché Herrschaft, Ordnung, Prinzip, der Anfang, der Erste) bezeichnet man ein System von Elementen, die einander über bzw.… … Deutsch Wikipedia
Hierarchisierung — Als Hierarchie ([hirarˈçiː] oder [hi̯erarˈçiː]) (griechisch ιεραρχία, ein Kompositum aus ιερή, hieré heilige und αρχή, arché Herrschaft, Ordnung, Prinzip, der Anfang, der Erste) bezeichnet man ein System von Elementen, die einander über bzw.… … Deutsch Wikipedia
Interaktionsdiagramm — In diesem Artikel oder Abschnitt fehlen folgende wichtige Informationen: Kritik (vgl. engl. Artikel); Bedeutung der UML; aktueller Stand (November 2007 wurde Version 2.1.2 vorgelegt, wie wurde sie aufgenommen?) Du kannst Wikipedia helfen, indem… … Deutsch Wikipedia
Monohierarchie — Als Hierarchie ([hirarˈçiː] oder [hi̯erarˈçiː]) (griechisch ιεραρχία, ein Kompositum aus ιερή, hieré heilige und αρχή, arché Herrschaft, Ordnung, Prinzip, der Anfang, der Erste) bezeichnet man ein System von Elementen, die einander über bzw.… … Deutsch Wikipedia
UML — In diesem Artikel oder Abschnitt fehlen folgende wichtige Informationen: Kritik (vgl. engl. Artikel); Bedeutung der UML; aktueller Stand (November 2007 wurde Version 2.1.2 vorgelegt, wie wurde sie aufgenommen?) Du kannst Wikipedia helfen, indem… … Deutsch Wikipedia
UML2 — In diesem Artikel oder Abschnitt fehlen folgende wichtige Informationen: Kritik (vgl. engl. Artikel); Bedeutung der UML; aktueller Stand (November 2007 wurde Version 2.1.2 vorgelegt, wie wurde sie aufgenommen?) Du kannst Wikipedia helfen, indem… … Deutsch Wikipedia
Finite-State-Machine — Abb.1 Beispiel eines EA Ein endlicher Automat (EA, auch Zustandsmaschine, englisch finite state machine (FSM)) ist ein Modell des Verhaltens, bestehend aus Zuständen, Zustandsübergängen und Aktionen. Ein Automat heißt endlich, wenn die Menge der… … Deutsch Wikipedia
