Nachbarschaft und Grad in Graphen

Stichpunkte

Allgemein
	kommt man nicht umhin lokale Eigenschaften mit eindeutigen Namen zu belegen
	Wenn man über Graphen und ihrem Aufbau oder deren innere Struktur spricht
	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 Beispiele zu illustrieren
	bevor er sich an tiefergehende graphentheoretische Artikel wagt. [Bearbeiten]
	Der Laie sollte aber zumindest die Begriffe Grad und Nachbarschaft unbedingt verinnerlichen
Definitionen
	Zwei Knoten heißen in einem ungerichteten Graphen (bzw
	wenn sie Element einer ungerichteten Kante (bzw
	Hypergraphen) G benachbart
	verbunden oder adjazent
	Hyperkante) von G sind
	Ein Knoten v und eine ungerichtete Kante e (bzw
	Hyperkante) heißen inzident
	falls v Element von e ist
	d.h. wenn sie einen gemeinsamen Knoten besitzen
	wenn sie nicht disjunkt sind
	Zwei ungerichtete Kanten heißen benachbart
	Ein Knoten x heißt Nachbar von einem Knoten y in einem ungerichteten Graphen (bzw
	wenn x und y zu einer Kante von G gehören
	Hypergraphen) G
	Mit NG(v) bezeichnet man die Menge aller Nachbarn eines Knotens v in G
	Ferner bezeichnet man mit NG(X) die Menge aller Nachbarn der Knoten von X in G
	NG(v) bzw
	NG(X) nennt man auch Nachbarschaft von v bzw
	XM
	it dG(v) bezeichnet man den Grad (bzw. die Valenz) des Knotens v in einem ungerichteten Graphen GD
	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 GD
	abei ist dG(v) in Graphen ohne Mehrfachkanten und Hypergraphen die Anzahl der Nachbarn von v
	as arithmetische Mittel aller Eckengrade von G wird als Durchschnittsgrad dG(G) bezeichnetE
	y) gerichtete Kante von G istM
	wenn (x
	in Knoten x heißt Vorgänger von y in einem gerichteten Graphen G
	it NG-(v) bezeichnet man die Menge aller Vorgänger eines Knotens v in GF
	erner bezeichnet man mit NG-(X) die Menge aller Vorgänger der Knoten von X in GN
	G-(v) bzwN
	G-(X) nennt man auch Vorgängermenge oder Eingangsmenge von v bzwX
	wenn (y
	x) gerichtete Kante von G ist
	Analog heißt x Nachfolger von y in G
	Mit NG+(v) bezeichnet man die Menge aller Nachfolger eines Knotens v in G
	Ferner bezeichnet man mit NG+(X) die Menge aller Nachfolger der Knoten von X in G
	NG+(v) bzw
	NG+(X) nennt man auch Nachfolgermenge oder Ausgangsmenge von v bzw
	XM
	it dG-(v) bezeichnet man den Eingangsgrad des Knotens v in einem gerichteten Graphen G und mit dG+(v) dessen AusgangsgradD
	v). In ungerichteten Graphen bzwH
	abei ist dG-(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 dG+(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
	ypergraphen nennt man einen Knoten isoliert
	wenn er keine Nachbarn besitztI
	n gerichteten Graphen nennt man einen Knoten isoliert
	wenn er keine Vorgänger und keine Nachfolger besitztF
	d- und d+ auch oft wegE
	lässt man den Index G bei N
	alls klar ist
	d
	N-
	N+
	um welchen Graphen es sich handelt
	in ungerichteter Graph (bzwH
	falls alle seine Knoten den selben Grad besitzenB
	ypergraph) G heißt regulär
	so bezeichnet man G als k-regulärE
	esitzen alle seine Knoten Grad k
	inen 3-regulären Graphen bezeichnet man auch als kubischE
	wenn alle Kanten von G die gleiche Anzahl Knoten enthaltenE
	in Hypergraph G heißt uniform
	nthalten alle Kanten von G genau k Knoten
	so nennt man G k-uniformE
	in gerichteter Graph G heißt regulär
	falls alle seine Knoten den selben Eingangs- und Ausgangsgrad besitzenB
	so bezeichnet man G als k-regulär.
	esitzen alle seine Knoten Eingangs- und Ausgangsgrad k

Dieser Artikel basiert auf dem Artikel Nachbarschaft und Grad in Graphen aus der freien Enzyklopädie wikipedia und steht unter der GNU Lizenz für freie Dokumentation. In der wikipedia ist eine Liste der Autoren verfügbar.