Yacas Reloaded - Freies Computer Algebra System

Inhalt

Grundlagen der Mathematik

Diskrete Mathematik

Kombinatorik

Graphentheorie

Typen von Graphen

Nachbarschaft und Grad

Wege, Pfade, Zyklen und

Kreise

Isomorphie von Graphen

Operationen auf Graphen

Zusammenhang

Durchlaufbarkeit von

Graphen

Färbung

Paarungen in Graphen

Schnitte

Knotenüberdeckungen,

Cliquen und stabile Mengen

Differentialgleichungen

Funktionalanalysis

Differentialgeometrie

Anbieterkennzeichnung

Weiterbildung für alle! Über 200 Fernlehrgänge an Deutschlands größter Fernschule!

Nachbarschaft und Grad in Graphen

Neu: Das Wurzelzieher Mathepedia Forum.

Jetzt registrieren und mit anderen Nutzern über Mathematik diskutieren!

Wenn man über Graphen und ihrem Aufbau oder deren innere Struktur spricht, kommt man nicht umhin lokale Eigenschaften mit eindeutigen Namen zu belegen. Es gibt praktisch keine graphentheoretische Abhandlung, die ohne die Begriffe Nachbarschaft und Grad auskommt. Andererseits sind diese Begriffe so trivial, dass es kaum interessante Ergebnisse gibt, die nur mit diesen Begriffen operieren. Dieser Artikel beschränkt sich daher darauf, diese Begriffe und leicht daraus ableitbare Graphenklassen zu erklären und diese an Beispielen zu illustrieren. Der Laie sollte aber zumindest die Begriffe Grad und Nachbarschaft unbedingt verinnerlichen, bevor er sich an tiefergehende graphentheoretische Artikel wagt.

Definitionen

Zwei Knoten heißen in einem ungerichteten Graphen (bzw. Hypergraphen) G benachbart, verbunden oder adjazent, wenn sie Element einer ungerichteten Kante (bzw. Hyperkante) von G sind. Ein Knoten v und eine ungerichtete Kante e (bzw. Hyperkante) heißen inzident, falls v Element von e ist. Zwei ungerichtete Kanten heißen benachbart, wenn sie nicht disjunkt sind, d.h. wenn sie einen gemeinsamen Knoten besitzen.

Ein Knoten x heißt Nachbar von einem Knoten y in einem ungerichteten Graphen (bzw. Hypergraphen) G, wenn x und y zu einer Kante von G gehören. Mit N_G (v) bezeichnet man die Menge aller Nachbarn eines Knotens v in G. Ferner bezeichnet man mit N_G (X) die Menge aller Nachbarn der Knoten von X in G. N_G (v) bzw. N_G (X) nennt man auch Nachbarschaft von v bzw. X.

Mit d_G (v) bezeichnet man den Grad (bzw. die Valenz) des Knotens v in einem ungerichteten Graphen G. Dabei ist d_G (v) in

Graphen ohne Mehrfachkanten und Hypergraphen die Anzahl der Nachbarn von v,
Graphen mit Mehrfachkanten die Summe der Vielfachheiten aller mit v inzidenten Kanten.

Den kleinsten Grad eines Knotens in G bezeichnet man dann als Minimalgrad von G, den größten Grad eines Knotens in G bezeichnet man als Maximalgrad von G. Das arithmetische Mittel aller Eckengrade von G wird als Durchschnittsgrad d_G (G) bezeichnet.

Ein Knoten x heißt Vorgänger von y in einem gerichteten Graphen G, wenn (x, y) gerichtete Kante von G ist. Mit N^-_G (v) bezeichnet man die Menge aller Vorgänger eines Knotens v in G. Ferner bezeichnet man mit N^-_G (X) die Menge aller Vorgänger der Knoten von X in G. N^-_G (v) bzw. N^-_G (X) nennt man auch Vorgängermenge oder Eingangsmenge von v bzw. X.

Analog heißt x Nachfolger von y in G, wenn (y, x) gerichtete Kante von G ist. Mit N⁺_G (v) bezeichnet man die Menge aller Nachfolger eines Knotens v in G. Ferner bezeichnet man mit N⁺_G (X) die Menge aller Nachfolger der Knoten von X in G. N⁺_G (v) bzw. N⁺_G (X) nennt man auch Nachfolgermenge oder Ausgangsmenge von v bzw. X.

Mit d^-_G (v) bezeichnet man den Eingangsgrad des Knotens v in einem gerichteten Graphen G und mit d⁺_G (v) dessen Ausgangsgrad. Dabei ist d^-_G (v) in

Graphen ohne Mehrfachkanten die Anzahl der Vorgänger von v,
Graphen mit Mehrfachkanten die Summe der Vielfachheiten aller Kanten in G der Form (v, x).

und d⁺_G (v) in

Graphen ohne Mehrfachkanten die Anzahl der Nachfolger von v,
Graphen mit Mehrfachkanten die Summe der Vielfachheiten aller Kanten in G der Form (x, v).

In ungerichteten Graphen bzw. Hypergraphen nennt man einen Knoten isoliert, wenn er keine Nachbarn besitzt. In gerichteten Graphen nennt man einen Knoten isoliert, wenn er keine Vorgänger und keine Nachfolger besitzt.

Falls klar ist, um welchen Graphen es sich handelt, lässt man den Index G bei N, N^- , N⁺ , d, d^- und d⁺ auch oft weg.

Ein ungerichteter Graph (bzw. Hypergraph) G heißt regulär, falls alle seine Knoten den selben Grad besitzen. Besitzen alle seine Knoten Grad k, so bezeichnet man G als k-regulär. Einen 3-regulären Graphen bezeichnet man auch als kubisch.

Ein Hypergraph G heißt uniform, wenn alle Kanten von G die gleiche Anzahl Knoten enthalten. Enthalten alle Kanten von G genau k Knoten, so nennt man G k-uniform.

Ein gerichteter Graph G heißt regulär, falls alle seine Knoten den selben Eingangs- und Ausgangsgrad besitzen. Besitzen alle seine Knoten Eingangs- und Ausgangsgrad k, so bezeichnet man G als k-regulär.

Ein Mathematiker ist eine Maschine, die Kaffee in Theoreme verwandelt.

Paul Erdös

Druckansicht

Impressum: Wurzelzieher Mathepedia • Thomas Steinfeld • Dorfplatz 25 • 17237 Blankensee • Tel.: 01734332309 (Vodafone/D2) • Email: matһе@wυrzеlzιeher.de

Amazon.de empfiehlt: