Kurs:Diskrete Mathematik (Osnabrück 2020)/Definitionsliste

Definition:Endliche Menge

Eine Menge ${}M$ heißt endlich mit ${}n$ Elementen, wenn es eine Bijektion

$\{1,\ldots ,n\}\longrightarrow M$

gibt.

Definition:Fakultät

Zu einer natürlichen Zahl ${}n$ nennt man die Zahl

${}n!:=n(n-1)(n-2)\cdots 3\cdot 2\cdot 1\,$

die Fakultät von ${}n$ (sprich ${}n$ Fakultät).

Definition:Permutation

Eine Permutation ${}\sigma$ auf einer Menge ${}M$ ist eine bijektive Abbildung

$\sigma \colon M\longrightarrow M.$

Definition:Potenzmenge

Zu einer Menge ${}M$ nennt man die Menge aller Teilmengen von ${}M$ die Potenzmenge von ${}M$. Sie wird mit

${\mathfrak {P}}\,(M)$

bezeichnet.

Definition:Binomialkoeffizient

Es seien ${}k$ und ${}n$ natürliche Zahlen mit ${}k\leq n$. Dann nennt man

${}{\binom {n}{k}}:={\frac {n!}{k!(n-k)!}}\,$

den Binomialkoeffizienten „${}n$ über ${}k$ “.

Definition:Verknüpfung

Eine Verknüpfung ${}\circ$ auf einer Menge ${}M$ ist eine Abbildung

$\circ \colon M\times M\longrightarrow M,\,(x,y)\longmapsto \circ (x,y)=x\circ y.$

Definition:Kommutative Verknüpfung

Eine Verknüpfung

$\circ \colon M\times M\longrightarrow M,\,(x,y)\longmapsto x\circ y,$

auf einer Menge ${}M$ heißt kommutativ, wenn für alle ${}x,y\in M$ die Gleichheit

${}x\circ y=y\circ x\,$

gilt.

Definition:Assoziative Verknüpfung

Eine Verknüpfung

$\circ \colon M\times M\longrightarrow M,\,(x,y)\longmapsto x\circ y,$

auf einer Menge ${}M$ heißt assoziativ, wenn für alle ${}x,y,z\in M$ die Gleichheit

${}(x\circ y)\circ z=x\circ (y\circ z)\,$

gilt.

Definition:Neutrales Element

Es sei eine Menge ${}M$ mit einer Verknüpfung

$\circ \colon M\times M\longrightarrow M,\,(x,y)\longmapsto x\circ y,$

gegeben. Dann heißt ein Element ${}e\in M$ neutrales Element der Verknüpfung, wenn für alle ${}x\in M$ die Gleichheit ${}x\circ e=x=e\circ x$ gilt.

Definition:Inverses Element

Es sei eine Menge ${}M$ mit einer Verknüpfung

$\circ \colon M\times M\longrightarrow M,\,(x,y)\longmapsto x\circ y,$

und einem neutralen Element ${}e\in M$ gegeben. Dann heißt zu einem Element ${}x\in M$ ein Element ${}y\in M$ inverses Element (zu ${}x$). wenn die Gleichheit

${}x\circ y=e=y\circ x\,$

gilt.

Definition:Monoid

Ein Monoid ist eine Menge ${}M$ zusammen mit einer Verknüpfung

$\circ \colon M\times M\longrightarrow M$

und einem ausgezeichneten Element ${}e\in M$ derart, dass folgende beiden Bedingungen erfüllt sind.

1. Die Verknüpfung ist assoziativ, d.h. es gilt

   ${}(x\circ y)\circ z=x\circ (y\circ z)\,$

   für alle ${}x,y,z\in M$.

2. ${}e$ ist neutrales Element der Verknüpfung, d.h. es gilt

   ${}x\circ e=x=e\circ x\,$

   für alle ${}x\in M$.

Definition:Kommutativer Halbring

Ein kommutativer Halbring ${}R$ ist eine Menge mit Verknüpfungen ${}+$ und ${}\cdot$ (genannt Addition und Multiplikation) und mit zwei ausgezeichneten Elementen ${}0$ und ${}1$ derart, dass folgende Bedingungen erfüllt sind:

1. Die Addition ist eine kommutative, assoziative Verknüpfung, für die ${}0$ das neutrale Element ist.
2. Die Multiplikation ist eine kommutative, assoziative Verknüpfung, für die ${}1$ das neutrale Element ist.
3. Es gilt das Distributivgesetz, also

   ${}a\cdot (b+c)=(a\cdot b)+(a\cdot c)\,$

   für alle

   ${}a,b,c\in R$.

Definition:Gruppe

Eine Menge ${}G$ mit einem ausgezeichneten Element ${}e\in G$ und mit einer Verknüpfung

$G\times G\longrightarrow G,\,(g,h)\longmapsto g\circ h,$

heißt Gruppe, wenn folgende Eigenschaften erfüllt sind.

1. Die Verknüpfung ist assoziativ, d.h. für alle ${}f,g,h\in G$ gilt

   ${}(f\circ g)\circ h=f\circ (g\circ h)\,.$

2. Das Element ${}e$ ist ein neutrales Element, d.h. für alle ${}g\in G$ gilt

   ${}g\circ e=g=e\circ g\,.$

3. Zu jedem ${}g\in G$ gibt es ein inverses Element, d.h. es gibt ein ${}h\in G$ mit

   ${}h\circ g=g\circ h=e\,.$

Definition:Kommutative Gruppe

Eine Gruppe ${}(G,e,\circ )$ heißt kommutativ (oder abelsch), wenn die Verknüpfung kommutativ ist, wenn also ${}x\circ y=y\circ x$ für alle ${}x,y\in G$ gilt.

Definition:Untergruppe

Es sei ${}(G,e,\circ )$ eine Gruppe. Eine Teilmenge ${}H\subseteq G$ heißt Untergruppe von ${}G$ wenn folgendes gilt.

1. ${}e\in H$.
2. Mit ${}g,h\in H$ ist auch ${}g\circ h\in H$.
3. Mit ${}g\in H$ ist auch ${}g^{-1}\in H$.

Definition:Ring

Eine Menge ${}R$ heißt ein Ring, wenn es zwei Verknüpfungen (genannt Addition und Multiplikation)

$+:R\times R\longrightarrow R{\text{ und }}\cdot :R\times R\longrightarrow R$

und (nicht notwendigerweise verschiedene) Elemente ${}0,1\in R$ gibt, die die folgenden Eigenschaften erfüllen.

1. Axiome der Addition
   1. Assoziativgesetz: Für alle ${}a,b,c\in R$ gilt ${}(a+b)+c=a+(b+c)$.
   2. Kommutativgesetz: Für alle ${}a,b\in R$ gilt ${}a+b=b+a$.
   3. ${}0$ ist das neutrale Element der Addition, d.h. für alle ${}a\in R$ ist ${}a+0=a$.
   4. Existenz des Negativen: Zu jedem ${}a\in R$ gibt es ein Element ${}b\in R$ mit ${}a+b=0$.
2. Axiome der Multiplikation
   1. Assoziativgesetz: Für alle ${}a,b,c\in R$ gilt ${}(a\cdot b)\cdot c=a\cdot (b\cdot c)$.
   2. ${}1$ ist das neutrale Element der Multiplikation, d.h. für alle ${}a\in R$ ist ${}a\cdot 1=1\cdot a=a$.
3. Distributivgesetz: Für alle ${}a,b,c\in R$ gilt ${}a\cdot (b+c)=(a\cdot b)+(a\cdot c)$ und ${}(b+c)\cdot a=(b\cdot a)+(c\cdot a)$.

Definition:Kommutativer Ring

Ein Ring ${}R$ heißt kommutativ, wenn die Multiplikation kommutativ ist.

Definition:Körper

Ein kommutativer Ring ${}R$ heißt Körper, wenn ${}R\neq 0$ ist und wenn jedes von ${}0$ verschiedene Element ein multiplikatives Inverses besitzt.

Definition:Relation

Es seien ${}M$ und ${}N$ Mengen. Eine Relation ${}R$ zwischen den Mengen ${}M$ und ${}N$ ist eine Teilmenge der Produktmenge ${}M\times N$, also ${}R\subseteq M\times N$.

Definition:Graph einer Abbildung

Es seien ${}L$ und ${}M$ Mengen und es sei

$F\colon L\longrightarrow M$

eine Abbildung. Dann nennt man

${}\Gamma =\Gamma _{F}={\left\{(x,F(x))\mid x\in L\right\}}\subseteq L\times M\,$

den Graphen der Abbildung ${}F$.

Definition:Linkseindeutige Relation

Eine Relation ${}R\subseteq M\times N$ heißt linkseindeutig, wenn es zu jedem ${}y\in N$ maximal ein ${}x\in M$ mit ${}(x,y)\in R$ gibt.

Definition:Rechtseindeutige Relation

Eine Relation ${}R\subseteq M\times N$ heißt rechtseindeutig, wenn es zu jedem ${}x\in M$ maximal ein ${}y\in N$ mit ${}(x,y)\in R$ gibt.

Definition:Linksvollständige Relation

Eine Relation ${}R\subseteq M\times N$ heißt linksvollständig, wenn es zu jedem ${}x\in M$ ein ${}y\in N$ mit ${}(x,y)\in R$ gibt.

Definition:Rechtsvollständige Relation

Eine Relation ${}R\subseteq M\times N$ heißt rechtsvollständig, wenn es zu jedem ${}y\in N$ ein ${}x\in M$ mit ${}(x,y)\in R$ gibt.

Definition:Relation auf einer Menge

Eine Relation ${}R$ auf einer Menge ${}M$ ist eine Teilmenge der Produktmenge ${}M\times M$, also ${}R\subseteq M\times M$.

Definition:Reflexiv

Eine Relation ${}R\subseteq M\times M$ auf einer Menge ${}M$ heißt reflexiv, wenn ${}(x,x)\in R$ für alle ${}x\in M$ gilt.

Definition:Transitiv

Eine Relation ${}R$ auf einer Menge ${}M$ heißt transitiv, wenn aus ${}xRy$ und ${}yRz$ stets ${}xRz$ folgt.

Definition:Symmetrisch

Eine Relation ${}R$ auf einer Menge ${}M$ heißt symmetrisch, wenn aus ${}xRy$ stets ${}yRx$ folgt.

Definition:Antisymmetrisch

Eine Relation ${}R$ auf einer Menge ${}M$ heißt antisymmetrisch, wenn aus ${}xRy$ und ${}yRx$ stets ${}x=y$ folgt.

Definition:Relationstreu

Es seien ${}(M,R)$ und ${}(N,S)$ Mengen mit darauf erklärten Relationen ${}R$ bzw. ${}S$. Man nennt eine Abbildung

$\varphi \colon M\longrightarrow N$

relationstreu (oder relationserhaltend), wenn für alle ${}x,y\in M$ mit ${}xRy$ auch ${}\varphi (x)S\varphi (y)$ gilt.

Definition:Ordnungsrelation

Eine Relation ${}\preccurlyeq$ auf einer Menge ${}I$ heißt Ordnungsrelation oder Ordnung, wenn folgende drei Bedingungen erfüllt sind.

1. Es ist ${}i\preccurlyeq i$ für alle ${}i\in I$.
2. Aus ${}i\preccurlyeq j$ und ${}j\preccurlyeq k$ folgt stets ${}i\preccurlyeq k$.
3. Aus ${}i\preccurlyeq j$ und ${}j\preccurlyeq i$ folgt ${}i=j$.

Definition:Lineare Ordnung

Eine Ordnungsrelation ${}\preccurlyeq$ auf einer Menge ${}I$ heißt lineare Ordnung (oder totale Ordnung), wenn zu je zwei Elementen ${}x,y\in I$ die Beziehung ${}x\preccurlyeq y$ oder ${}y\preccurlyeq x$ gilt.

Definition:Angeordneter Ring

Ein kommutativer Ring heißt angeordnet, wenn es eine totale Ordnung ${}\geq$ auf ${}R$ gibt, die die beiden Eigenschaften

1. Aus ${}a\geq b$ folgt ${}a+c\geq b+c$ für beliebige ${}a,b,c\in R$,
2. Aus ${}a\geq 0$ und ${}b\geq 0$ folgt ${}ab\geq 0$ für beliebige ${}a,b\in R$,

erfüllt.

Definition:Teilen (${}\mathbb {N}$)

Man sagt, dass die natürliche Zahl ${}a$ die natürliche Zahl ${}b$ teilt (oder dass ${}b$ von ${}a$ geteilt wird, oder dass ${}b$ ein Vielfaches von ${}a$ ist), wenn es eine natürliche Zahl ${}c$ derart gibt, dass ${}b=c\cdot a$ ist. Man schreibt dafür auch ${}a{|}b$.

Definition:Produktordnung

Es sei ${}(M_{i},\leq _{i})$, ${}i\in I$, eine Familie von geordneten Mengen. Dann nennt man die auf der Produktmenge ${}M=\prod _{i\in I}M_{i}$ durch

${}(x_{i})_{i\in I}\leq (y_{i})_{i\in I}\,,$

falls

${}x_{i}\leq _{i}y_{i}\,$

für alle ${}i\in I$ gilt, die Produktordnung.

Definition:Ordnungstreu

Es seien ${}(M_{1},\leq _{1})$ und ${}(M_{2},\leq _{2})$ zwei Mengen, auf denen jeweils eine Ordnung definiert ist. Eine Abbildung

$F\colon M_{1}\longrightarrow M_{2},\,x\longmapsto F(x),$

heißt ordnungstreu (oder monoton), wenn für alle ${}x,x'\in M_{1}$ mit ${}x\leq _{1}x'$ stets auch ${}F(x)\leq _{2}F(x')$ gilt.

Definition:Ordnungsvolltreu

Es seien ${}(M_{1},\leq _{1})$ und ${}(M_{2},\leq _{2})$ zwei Mengen, auf denen jeweils eine Ordnung definiert ist. Eine Abbildung

$F\colon M_{1}\longrightarrow M_{2},\,x\longmapsto F(x),$

heißt ordnungsvolltreu, wenn für alle ${}x,x'\in M_{1}$ genau dann ${}x\leq _{1}x'$ gilt, wenn ${}F(x)\leq _{2}F(x')$ gilt.

Definition:Monoton fallende Abbildung

Es seien ${}(M_{1},\leq _{1})$ und ${}(M_{2},\leq _{2})$ zwei Mengen, auf denen jeweils eine Ordnung definiert ist. Eine Abbildung

$F\colon M_{1}\longrightarrow M_{2},\,x\longmapsto F(x),$

heißt monoton fallend, wenn für alle ${}x,x'\in M_{1}$ mit ${}x\leq _{1}x'$ stets ${}F(x)\geq _{2}F(x')$ gilt.

Definition:Größtes Element

Es sei ${}(I,\preccurlyeq )$ eine geordnete Menge. Ein Element ${}x\in I$ heißt größtes Element von ${}I$, wenn ${}y\preccurlyeq x$ für jedes ${}y\in I$ gilt.

Definition:Kleinstes Element

Es sei ${}(I,\preccurlyeq )$ eine geordnete Menge. Ein Element ${}x\in I$ heißt kleinstes Element von ${}I$, wenn ${}x\preccurlyeq y$ für jedes ${}y\in I$ gilt.

Definition:Maximales Element

Es sei ${}(I,\preccurlyeq )$ eine geordnete Menge. Ein Element ${}x\in I$ heißt maximal (in ${}I$) oder ein maximales Element (von ${}I$), wenn es kein Element ${}y\in I$, ${}y\neq x$, mit ${}x\preccurlyeq y$ gibt.

Definition:Minimum

Es sei ${}(I,\preccurlyeq )$ eine geordnete Menge. Ein Element ${}x\in I$ heißt minimal (in ${}I$) oder ein minimales Element (von ${}I$), wenn es kein Element ${}y\in I$, ${}y\neq x$, mit ${}y\preccurlyeq x$ gibt.

Definition:Obere Schranke

Es sei ${}(I,\preccurlyeq )$ eine geordnete Menge und ${}J\subseteq I$ eine Teilmenge. Ein Element ${}s\in I$ heißt obere Schranke für ${}J$, wenn ${}y\preccurlyeq s$ für jedes ${}y\in J$ gilt.

Definition:Untere Schranke

Es sei ${}(I,\preccurlyeq )$ eine geordnete Menge und ${}J\subseteq I$ eine Teilmenge. Ein Element ${}s\in I$ heißt untere Schranke für ${}J$, wenn ${}s\preccurlyeq x$ für jedes ${}x\in J$ gilt.

Definition:Supremum

Es sei ${}(I,\preccurlyeq )$ eine geordnete Menge und ${}J\subseteq I$ eine Teilmenge. Ein Element ${}s\in I$ heißt Supremum von ${}J$, wenn ${}s$ die kleinste obere Schranke von ${}J$ ist.

Definition:Infimum

Es sei ${}(I,\preccurlyeq )$ eine geordnete Menge und ${}J\subseteq I$ eine Teilmenge. Ein Element ${}s\in I$ heißt Infimum von ${}J$, wenn ${}s$ die größte untere Schranke von ${}J$ ist.

Definition:Gemeinsamer Teiler

Es seien ${}a_{1},\ldots ,a_{k}$ natürliche Zahlen. Dann heißt eine natürliche Zahl ${}t$ gemeinsamer Teiler der ${}a_{1},\ldots ,a_{k}$, wenn ${}t$ jedes ${}a_{i}$ teilt für ${}i=1,\ldots ,k$.

Definition:Gemeinsamer Teiler

Es seien ${}a_{1},\ldots ,a_{k}$ natürliche Zahlen. Dann heißt eine natürliche Zahl ${}g$ der größte gemeinsame Teiler der ${}a_{1},\ldots ,a_{k}$, wenn ${}g$ ein gemeinsamer Teiler der ${}a_{i}$ ist und wenn jeder gemeinsame Teiler ${}t$ der ${}a_{i}$ dieses ${}g$ teilt.

Definition:Gemeinsames Vielfaches

Zu einer Menge von natürlichen Zahlen

$a_{1},\ldots ,a_{k}$

heißt eine natürliche Zahl ${}b$ ein gemeinsames Vielfaches, wenn ${}b$ ein Vielfaches von jedem ${}a_{i}$ ist, also von jedem ${}a_{i}$ geteilt wird.

Definition:Kleinstes gemeinsames Vielfaches

Zu einer Menge von natürlichen Zahlen

$a_{1},\ldots ,a_{n}$

heißt eine natürliche Zahl ${}b$ das kleinste gemeinsame Vielfache dieser Zahlen, wenn ${}b$ ein gemeinsames Vielfaches der ${}a_{i}$ ist und wenn jedes gemeinsame Vielfache der Zahlen ein Vielfaches von ${}b$ ist.

Definition:Euklidische Restfolge

Es seien zwei ganze Zahlen ${}a,b$ (mit ${}b\neq 0$) gegeben. Dann nennt man die durch die Anfangsbedingungen ${}r_{0}=a$ und ${}r_{1}=b$ und die mittels der Division mit Rest

${}r_{i}=q_{i}r_{i+1}+r_{i+2}\,$

rekursiv bestimmte Folge ${}r_{i}$ die Folge der euklidischen Reste.

Definition:Verband

Eine geordnete Menge ${}(M,\leq )$ mit der Eigenschaft, dass für je zwei Elemente ${}x,y\in M$ ein Infimum ${}x\sqcap y$ und ein Supremum ${}x\sqcup y$ existiert, heißt Verband.

Definition:Algebraischer Verband

Eine Menge ${}M$ mit zwei kommutativen und assoziativen Verknüpfungen ${}\sqcup$ und ${}\sqcap$ heißt algebraischer Verband, wenn die Absorptionsgesetze

${}x\sqcup (x\sqcap y)=x\,$

und

${}x\sqcap (x\sqcup y)=x\,$

gelten.

Definition:Zugehörige Ordnung (Verband)

In einem algebraischen Verband ${}(M,\sqcap ,\sqcup )$ nennt man die durch

${}y\geq x\,,$

falls

${}x\sqcap y=x\,,$

definierte Ordnung, die zugehörige Ordnung.

Definition:Beschränkter Verband

Ein Verband ${}M$ heißt beschränkt, wenn es in ihm ein kleinstes Element ${}0$ und ein größtes Element ${}1$ gibt.

Definition:Komplementärer Verband

Ein beschränkter Verband ${}M$ heißt komplementär, wenn es zu jedem ${}x\in M$ ein ${}y\in M$ mit ${}x\sqcap y=0$ und ${}x\sqcup y=1$ gibt.

Definition:Distributiver Verband

Ein Verband ${}M$ heißt distributiv, wenn in ihm die Distributivgesetze

${}x\sqcap {\left(y\sqcup z\right)}={\left(x\sqcap y\right)}\sqcup {\left(x\sqcap z\right)}\,$

und

${}x\sqcup {\left(y\sqcap z\right)}={\left(x\sqcup y\right)}\sqcap {\left(x\sqcup z\right)}\,$

gelten.

Definition:Boolescher Verband

Ein Verband ${}M$ heißt boolesch, wenn er komplementär und distributiv ist.

Definition:Atom

Es sei ${}(M,\preccurlyeq )$ eine geordnete Menge mit einem kleinsten Element ${}0$. Ein Element ${}a\in M$ heißt Atom, wenn ${}a\neq 0$ ist und die Beziehung ${}x\preccurlyeq a$ nur für ${}x=0$ und ${}x=a$ gilt.

Definition:Äquivalenzrelation

Eine Äquivalenzrelation auf einer Menge ${}M$ ist eine Relation ${}R\subseteq M\times M$, die die folgenden drei Eigenschaften besitzt (für beliebige ${}x,y,z\in M$).

1. Es ist ${}x\sim x$ (reflexiv).
2. Aus ${}x\sim y$ folgt ${}y\sim x$ (symmetrisch).
3. Aus ${}x\sim y$ und ${}y\sim z$ folgt ${}x\sim z$ (transitiv).

Dabei bedeutet ${}x\sim y$, dass das Paar ${}(x,y)$ zu ${}R$ gehört.

Definition:Äquivalenzklasse

Es sei ${}R\subseteq M\times M$ eine Äquivalenzrelation und ${}x\in M$. Dann ist

${}[x]:={\left\{y\in M\mid (x,y)\in R\right\}}\,$

die Äquivalenzklasse von ${}x$ bezüglich ${}R$.

Definition:Repräsentantensystem

Es sei ${}\sim$ eine Äquivalenzrelation auf einer Menge ${}M$. Eine Teilmenge ${}T\subseteq M$ heißt ein Repräsentantensystem für die Äquivalenzrelation, wenn es für jede Äquivalenzklasse genau ein Element in ${}T$ aus dieser Klasse gibt.

Definition:Quotientenmenge

Es sei ${}R\subseteq M\times M$ eine Äquivalenzrelation. Dann heißt

${}M/R:={\left\{[x]\mid x\in M\right\}}\,$

die Quotientenmenge von ${}R$.

Definition:Kanonische Projektion

Es sei ${}R\subseteq M\times M$ eine Äquivalenzrelation und ${}M/R$ die Quotientenmenge. Die Abbildung

$q_{R}\colon M\longrightarrow M/R,\,x\longmapsto [x],$

heißt kanonische Projektion von ${}R$.

Definition:Gruppenhomomorphismus

Es seien ${}(G,\circ ,e_{G})$ und ${}(H,\circ ,e_{H})$ Gruppen. Eine Abbildung

$\psi \colon G\longrightarrow H$

heißt Gruppenhomomorphismus, wenn die Gleichheit

${}\psi (g\circ g')=\psi (g)\circ \psi (g')\,$

für alle ${}g,g'\in G$ gilt.

Definition:Ringhomomorphismus

Es seien ${}R$ und ${}S$ Ringe. Eine Abbildung

$\varphi \colon R\longrightarrow S$

heißt Ringhomomorphismus, wenn folgende Eigenschaften gelten:

1. ${}\varphi (a+b)=\varphi (a)+\varphi (b)$.
2. ${}\varphi (1)=1$.
3. ${}\varphi (a\cdot b)=\varphi (a)\cdot \varphi (b)$.

Definition:Äquivalenzrelation zu einer Untergruppe

Es sei ${}(G,0,+)$ eine kommutative Gruppe und ${}H\subseteq G$ eine Untergruppe. Für Elemente ${}x,y\in G$ setzen wir ${}x\sim _{H}y$ (und sagen, dass ${}x$ und ${}y$ äquivalent sind), wenn ${}x-y\in H$.

Definition:Restklassengruppe

Es sei ${}(G,0,+)$ eine kommutative Gruppe und ${}H\subseteq G$ eine Untergruppe. Die Quotientenmenge

$G/H$

mit der aufgrund von Satz 12.5 eindeutig bestimmten Gruppenstruktur heißt Restklassengruppe von ${}G$ modulo ${}H$. Die Elemente ${}[g]\in G/H$ heißen Restklassen. Für eine Restklasse ${}[g]$ heißt jedes Element ${}g'\in G$ mit ${}[g']=[g]$ ein Repräsentant von ${}[g]$.

Definition:Ideal

Eine Teilmenge ${}{\mathfrak {a}}$ eines kommutativen Ringes ${}R$ heißt Ideal, wenn die folgenden Bedingungen erfüllt sind:

1. ${}0\in {\mathfrak {a}}$.
2. Für alle ${}a,b\in {\mathfrak {a}}$ ist auch ${}a+b\in {\mathfrak {a}}$.
3. Für alle ${}a\in {\mathfrak {a}}$ und ${}r\in R$ ist auch ${}ra\in {\mathfrak {a}}$.

Definition:Multinomialkoeffizient

Es sei ${}n$ eine natürliche Zahl und ${}r_{1},\ldots ,r_{k}$ natürliche Zahlen mit ${}\sum _{j=1}^{k}r_{j}=n$. Dann nennt man

${}{\binom {n}{r_{1},\dotsc ,r_{k}}}:={\frac {n!}{r_{1}!\cdots r_{k}!}}\,$

den Multinomialkoeffizienten ${}n$ über ${}r_{1},\ldots ,r_{k}$.

Definition:Partition

Es sei ${}M$ eine Menge. Eine Teilmenge ${}P\subseteq {\mathfrak {P}}\,(M)$ heißt Partition von ${}M$, falls die folgenden Bedingungen erfüllt sind.

1. Für alle ${}A\in P$ gilt ${}A\neq \emptyset$.
2. Für ${}A,B\in P$, ${}A\neq B$, gilt ${}A\cap B=\emptyset$.
3. Die Elemente von ${}P$ bilden eine Überdeckung von ${}M$, d.h. jedes Element von ${}M$ liegt in mindestens einem Element von ${}P$.

Definition:Stirling-Zahlen zweiter Art

Die Anzahl der Partitionen einer ${}n$-elementigen Menge ${}M$ in ${}k$ Blöcke heißt Stirling-Zahl zweiter Art. Sie wird mit ${}S({n},{k})$ bezeichnet.

Definition:Bellzahl

Die Anzahl der Partitionen einer ${}n$-elementigen Menge heißt Bellzahl und wird mit ${}B_{n}$ bezeichnet.

Definition:Ungerichteter Graph

Ein ungerichteter Graph auf einer Menge ${}V$ (die die Eckpunktmenge des Graphen heißt) besteht aus einer gewissen Auswahl an zweielementigen Teilmengen (die die Kantenmenge des Graphen heißt) von ${}V$.

Definition:Nachbarschaft (Graph)

Zu einem Punkt ${}v\in V$ in einem Graphen ${}G=(V,E)$ nennt man

${}N(v)={\left\{u\in V\mid \{u,v\}\in E\right\}}\,$

die Nachbarschaft von ${}v$.

Definition:Vollständiger Graph

Ein Graph auf einer Menge ${}V$ heißt vollständig, wenn je zwei Punkte miteinander durch eine Kante verbunden sind.

Definition:Kantenfreier Graph

Ein Graph ${}G=(V,E)$ heißt kantenfrei, wenn die Kantenmenge ${}E$ leer ist.

Definition:Linearer Graph

Ein Graph ${}G=(V,E)$ heißt linear, wenn es eine Auflistung ${}v_{1},\ldots ,v_{n}$ aller Knoten derart gibt, dass die Kantenmenge gleich ${}\{v_{i},v_{i+1}\}$, ${}i=1,2,\ldots ,n-1$, ist.

Definition:Sterngraph

Ein Graph ${}G=(V,E)$ heißt Sterngraph, wenn es in ihm einen Knoten (das Zentrum) gibt, der mit allen anderen Knoten verbunden ist und dies die einzigen Kanten des Graphen sind.

Definition:Grad (Graphentheorie)

Zu einem Punkt ${}v\in V$ in einem Graphen nennt man die Anzahl der Kanten, die an ${}v$ anliegen, den Grad von ${}v$. Er wird mit ${}d(v)$ bezeichnet.

Definition:Isolierter Punkt

Ein Punkt ${}v\in V$ eines Graphen mit Grad ${}0$ heißt isoliert.

Definition:Blatt

Ein Punkt ${}v\in V$ eines Graphen mit Grad ${}1$ heißt Blatt.

Definition:Minimalgrad

Zu einem Graphen nennt man

${}\delta (G)={\min {\left(d(v),v\in V\right)}}\,$

den Minimalgrad des Graphen.

Definition:Maximalgrad

Zu einem Graphen nennt man

${}\Delta (G)={\max {\left(d(v),v\in V\right)}}\,$

den Maximalgrad des Graphen.

Definition:Vollständiger Graph

Ein Graph auf einer Menge ${}V$ heißt ${}r$-regulär, wenn jeder Punkt den Grad ${}r$ besitzt.

Definition:Untergraph

Ein Graph ${}(W,F)$ heißt Untergraph eines Graphen ${}(V,E)$, wenn ${}W\subseteq V$, ${}F\subseteq E$ und die Kanten aus ${}F$ nur Bezug auf Punkte aus ${}W$ nehmen.

Definition:Voller Untergraph

Ein Untergraph ${}(W,F)\subseteq (V,E)$ heißt voll, wenn jede Kante aus ${}E$, die Punkte aus ${}W$ verbindet, auch eine Kante in ${}F$ ist.

Definition:Homomorphismus von Graphen

Es seien ${}G=(V,E)$ und ${}H=(W,F)$ Graphen. Eine Abbildung ${}\varphi \colon V\rightarrow W$ mit der Eigenschaft, dass aus ${}vv'\in E$ stets ${}\varphi (v)\varphi (v')\in F$ folgt, heißt Graphhomomorphismus.

Definition:Isomorphismus von Graphen

Es seien ${}G=(V,E)$ und ${}H=(W,F)$ Graphen. Ein Graphhomomorphismus ${}\varphi \colon G\rightarrow H$ heißt Isomorphismus, wenn es einen Graphhomomorphismus

$\psi \colon H\longrightarrow G$

derart gibt, dass

${}\psi \circ \varphi =\operatorname {Id} _{V}\,$

und

${}\varphi \circ \psi =\operatorname {Id} _{W}\,$

gilt.

Definition:Isomorphe Graphen

Zwei Graphen ${}G=(V,E)$ und ${}H=(W,F)$ heißen isomorph, wenn es einen Graphisomorphismus ${}\varphi \colon G\rightarrow H$ gibt.

Definition:Schwacher Graphhomomorphismus

Es seien ${}G=(V,E)$ und ${}H=(W,F)$ Graphen. Eine Abbildung ${}\varphi \colon V\rightarrow W$ mit der Eigenschaft, dass aus ${}vv'\in E$ entweder ${}\varphi (v)=\varphi (v')$ oder aber ${}\varphi (v)\varphi (v')\in F$ folgt, heißt schwacher Graphhomomorphismus.

Definition:Graphautomorphismus

Es sei ${}G=(V,E)$ ein Graph. Ein Isomorphismus ${}\varphi \colon G\rightarrow G$ heißt Automorphismus.

Definition:Automorphismengruppe (Graph)

Zu einem Graphen ${}G$ nennt man die Gruppe aller Automorphismen

$\varphi \colon G\longrightarrow G$

die Automorphismengruppe von ${}G$. Sie wird mit ${}\operatorname {Aut} \,G$ bezeichnet.

Definition:Homogener Graph

Ein Graph ${}G=(V,E)$ heißt homogen, wenn es zu je zwei Knotenpunkten ${}u,v\in V$ einen Automorphismus

$\varphi \colon G\longrightarrow G$

mit

${}\varphi (u)=v\,$

gibt.

Definition:Starrer Graph

Ein Graph ${}G=(V,E)$ heißt starr, wenn die Automorphismengruppe von ${}G$ trivial ist.

Definition:Komplementärer Graph

Zu einem Graphen ${}G=(V,E)$ nennt man den Graphen ${}(V,{\mathfrak {P}}_{2}\,(V)\setminus E)$ den komplementären Graphen (oder Komplementärgraph). Er wird mit ${}G^{c}$ bezeichnet.

Definition:Restgraph

Zu einem Graphen ${}G=(V,E)$ und einer Teilmenge ${}F\subseteq E$ der Kantenmenge versteht man unter ${}G\setminus F$ denjenigen Graphen, dessen Punktemenge ${}V$ ist und dessen Kantenmenge aus ${}E\setminus F$ besteht.

Definition:Kantengraph

Es sei ${}G=(V,E)$ ein Graph. Man nennt denjenigen Graphen, dessen Knotenmenge die Kantenmenge ${}E$ von ${}G$ ist und bei dem zwei Knoten ${}L_{1}$ und ${}L_{2}$ (also Kanten aus ${}G$) genau dann durch eine Kante verbunden werden, wenn ${}L_{1}$ und ${}L_{2}$ einen gemeinsamen Punkt in ${}V$ besitzen, den Kantengraphen zu ${}G$.

Definition:Bildgraph

Es sei ${}G=(V,E)$ ein Graph, ${}M$ eine Menge und ${}\varphi \colon V\rightarrow M$ eine Abbildung. Unter dem Bildgraphen zu ${}\varphi$ versteht man denjenigen Graphen, dessen Knotenmenge durch das Bild ${}W=\varphi (V)\subseteq M$ von ${}\varphi$ und dessen Kantenmenge durch

${}F={\left\{\{\varphi (u),\varphi (v)\}\mid \{u,v\}\in E,\,\varphi (u)\neq \varphi (v)\right\}}\,$

gegeben ist.

Definition:Quotientengraph

Es sei ${}G=(V,E)$ ein Graph und sei ${}\sim$ eine Äquivalenzrelation auf ${}V$. Dann nennt man die Quotientenmenge ${}V/\sim$, versehen mit der Bildgraphstruktur zur kanonischen Abbildung

$V\longrightarrow V/\sim ,$

den Quotientengraphen zu ${}\sim$. Er wird mit ${}G/\sim$ bezeichnet.

Definition:Kontraktionsgraph

Es sei ${}G=(V,E)$ ein Graph und ${}e\in E$ eine Kante, die die Knotenpunkte ${}u$ und ${}v$ verbindet. Man nennt denjenigen Graphen mit der Knotenmenge ${}V'=V/e$, bei der ${}u$ und ${}v$ miteinander identifiziert werden, und bei dem die Kantenmenge ${}E'$ aus den Bildkanten zur Kontraktionsabbildung ${}V\rightarrow V/e$ besteht, den Kontraktionsgraphen zu ${}e\in G$. Er wird mit ${}G/e$ bezeichnet.

Definition:Disjunkte Vereinigung (Graphen)

Zu zwei Graphen ${}G=(V,E)$ und ${}H=(W,F)$ mit disjunkten Knotenmengen ${}V$ und ${}W$ nennt man den Graphen mit der Knotenmenge ${}V\uplus W$ und der Kantenmenge ${}E\uplus F\subseteq {\mathfrak {P}}\,(V\uplus W)$ die disjunkte Vereinigung der Graphen.

Definition:Kartesisches Produkt (Graph)

Zu zwei Graphen ${}G=(V,E)$ und ${}H=(W,F)$ nennt man den Graphen mit Knotenmenge ${}V\times W$, wobei zwischen zwei Knoten ${}(v_{1},w_{1})$ und ${}(v_{2},w_{2})$ genau dann eine Kante besteht, wenn entweder ${}v_{1}=v_{2}$ und ${}\{w_{1},w_{2}\}\in F$ oder ${}w_{1}=w_{2}$ und ${}\{v_{1},v_{2}\}\in E$ gilt, das kartesische Produkt der Graphen.

Definition:Weg

Ein Weg in einem Graphen ist eine Folge ${}v_{1},v_{2},\ldots ,v_{m}$ von Knoten derart, dass ${}v_{i}v_{i+1}$ für alle ${}i$ eine Kante ist.

Definition:Zusammenhängender Graph

Ein Graph ${}(V,E)$ heißt zusammenhängend, wenn es zu je zwei Punkten ${}u,v\in G$ einen Weg gibt, der ${}u$ und ${}v$ verbindet.

Definition:Zusammenhangskomponente (Graph)

Zu einem Punkt ${}v\in V$ in einem Graphen nennt man

${}Z(v)={\left\{u\in V\mid {\text{es gibt einen Weg, der }}u{\text{ und }}v{\text{ verbindet }}\right\}}\,$

die Zusammenhangskomponente von ${}v$.

Definition:Weglänge (Graph)

Unter der Länge eines Weges in einem Graphen versteht man die Anzahl seiner Kanten.

Definition:Abstand (Graph)

Zu zwei Knotenpunkten ${}u$ und ${}v$ in einem zusammenhängenden Graphen versteht man unter dem Abstand ${}d(u,v)$ die minimale Länge eines verbindenden Weges von ${}u$ nach ${}v$.

Definition:Durchmesser (Graph)

Unter dem Durchmesser eines zusammenhängenden Graphen ${}G=(V,E)$ versteht man das Maximum über alle Abstände ${}d(u,v)$ zu ${}u,v\in V$.

Definition:Radius (Graph)

Unter dem Radius eines zusammenhängenden Graphen ${}G=(V,E)$ versteht man den Ausdruck

$\operatorname {min} \left(\operatorname {max} \left(d(u,v){|}u\in V\right){|}v\in V\right).$

Definition:Exzentrizität (Graph)

Zu einem Knotenpunkt ${}v\in V$ eines zusammenhängenden Graphen ${}G=(V,E)$ nennt man

${}e(v)=\operatorname {max} \left(d(u,v){|}u\in V\right)\,$

die Exzentrizität von ${}v$.

Definition:Zyklus

Ein Weg ${}v_{1},\ldots ,v_{m}$ in einem Graphen ${}(V,E)$ heißt Zyklus, wenn ${}v_{1}=v_{m}$ ist.

Definition:Kreis (Graph)

Ein Kreis in einem Graphen ist ein Zyklus der Länge ${}\geq 3$ ohne Wiederholungen.

Definition:Rundgang

Ein Graph ${}G$ heißt Rundgang, wenn es in ihm einen Kreis ${}v_{1},v_{2},\ldots ,v_{m}=v_{1}$ gibt, der alle Knotenpunkte und alle Kanten genau einmal durchläuft.

Definition:Taille

Die Taille eines zyklischen Graphen ist die kürzeste Länge eines Kreises in ${}G$.

Definition:Umfang

Der Umfang eines zyklischen Graphen ${}G$ ist die längste Länge eines Kreises in ${}G$.

Definition:Wald

Ein Graph ohne Kreis heißt Wald

Definition:Baum

Ein zusammenhängender Wald heißt Baum.

Definition:Aufspannender Baum

Ein Untergraph ${}B\subseteq G$ eines Graphen ${}G=(V,E)$ heißt aufspannender Baum von ${}G$, wenn ${}B$ ein Baum mit der vollen Knotenmenge ${}V$ ist.

Definition:Matroid

Zu einer endlichen Menge ${}E$ heißt eine Teilmenge

${}{\mathcal {M}}\subseteq {\mathfrak {P}}\,(E)\,$

ein Matroid, wenn folgende Bedingungen erfüllt sind.

1. Es ist ${}\emptyset \in {\mathcal {M}}$.
2. Aus ${}A\in {\mathcal {M}}$ und ${}B\subseteq A$ folgt ${}B\in {\mathcal {M}}$.
3. Wenn ${}A,B\in {\mathcal {M}}$ mit

   ${}{\#\left(A\right)}={\#\left(B\right)}+1\,,$

   so gibt es ein ${}a\in A\setminus B$ derart, dass ${}B\cup \{a\}\in {\mathcal {M}}$.

Definition:Basis (Matroid)

In einem Matroid ${}{\mathcal {M}}$ auf einer Menge ${}I$ nennt man die maximalen Mengen aus ${}{\mathcal {M}}$ Basen.

Definition:Rang (Matroid)

In einem Matroid ${}{\mathcal {M}}$ auf einer Menge ${}I$ nennt man die gemeinsame Anzahl der Elemente in einer jeden Basis von ${}{\mathcal {M}}$ den Rang des Matroids.

Definition:Aufspannender Wald

Ein Untergraph ${}W\subseteq G$ eines Graphen ${}G=(V,E)$ heißt aufspannender Wald von ${}G$, wenn ${}W$ ein Wald ist, dessen Bäume mit den Zusammenhangskomponenten von ${}V$ übereinstimmen.

Definition:Multigraph

Ein Multigraph ${}(V,E,\theta )$ besteht aus einer Knotenmenge ${}V$, einer Kantenmenge ${}E$ und einer Abbildung

$\theta \colon E\longrightarrow {\mathfrak {P}}_{2}\,(V).$

Definition:Adjazenzmatrix

Zu einem Graphen ${}G=(V,E)$ versteht man unter der Adjazenzmatrix diejenige ${}V\times V$- Matrix, deren Einträge durch

${}a_{u,v}={\begin{cases}1,\,{\text{falls }}\{u,v\}\in E,\\0\,{\text{ sonst}},\end{cases}}\,$

gegeben sind.

Definition:Charakteristisches Polynom (Graph)

Zu einem Graphen nennt man das charakteristische Polynom der Adjazenzmatrix das charakteristische Polynom von ${}G$.

Definition:Inzidenzmatrix

Es sei ${}G=(V,E)$ ein Graph. Unter der Inzidenzmatrix zu ${}G$ verstehen wir die ${}V\times E$- Matrix, deren Einträge durch

${}b_{v,e}:={\begin{cases}1,\,{\text{falls }}v\in e,\\0{\text{ sonst}}\,,\end{cases}}\,$

gegeben sind.

Definition:Gradmatrix

Es sei ${}G=(V,E)$ ein Graph. Unter der Gradmatrix zu ${}G$ verstehen wir die ${}V\times V$- Diagonalmatrix, deren Diagonaleintrag an der Stelle ${}(v,v)$ durch den Grad im Knotenpunkt ${}v$ gegeben ist.

Definition:Laplace-Matrix

Zu einem Multigraphen ${}G$ versteht man unter der Laplace-Matrix ${}L$ die Differenz

${}L=D-A\,$

aus Gradmatrix ${}D$ und Adjazenzmatrix ${}A$.

Definition:Bipartiter Graph

Ein Graph ${}G=(V,E)$ heißt bipartit, wenn es eine disjunkte Zerlegung

${}V=A\uplus B\,$

derart gibt, dass es nur Kanten zwischen ${}A$ und ${}B$ gibt.

Definition:Vollständiger bipartiter Graph

Der vollständige bipartite Graph ${}K_{m,n}$ ist derjenige Graph, dessen Knotenmenge aus der disjunkten Vereinigung einer ${}m$-elementigen Menge ${}A$ und einer ${}n$-elementigen Menge ${}B$ besteht und dessen Kantenmenge durch

${}E={\left\{\{a,b\}\mid a\in A,\,b\in B\right\}}\,$

gegeben ist.

Definition:Paarung (Graph)

Eine Paarung in einem Graphen ${}G=(V,E)$ ist eine Kantenmenge ${}P\subseteq E$, wobei die Kanten aus ${}P$ zueinander disjunkt sind.

Definition:Abgedeckter Knotenpunkt

Wir sagen, dass eine Paarung ${}P$ in einem Graphen ${}G=(V,E)$ einen Knotenpunkt ${}v\in V$ abdeckt, wenn es eine Kante aus ${}P$ gibt, zu der ${}v$ gehört.

Definition:Paarung (Teilknotenmenge)

Eine Paarung ${}P\subseteq E$ in einem Graphen ${}G$ heißt Paarung für eine Teilmenge ${}S\subseteq V$, wenn jeder Knoten aus ${}S$ von einer Kante aus ${}P$ abgedeckt wird.

Definition:Perfekte Paarung

Eine Paarung ${}P\subseteq E$ in einem Graphen ${}G$ heißt perfekt, wenn die Kanten der Paarung jeden Knoten des Graphen abdecken.

Definition:Maximale Paarung

Eine Paarung ${}P\subseteq E$ in einem Graphen heißt maximal, wenn jedes ${}P'$ mit ${}P\subset P'\subseteq E$ keine Paarung ist.

Definition:Optimale Paarung

Eine Paarung ${}P\subseteq E$ in einem Graphen ${}G$ heißt optimal, wenn sie unter allen Paarungen von ${}G$ die größtmögliche Anzahl von Kanten enthält.

Definition:Paarungszahl

Die Paarungszahl eines bipartiten Graphen ${}G=A\uplus B$ ist die größtmögliche Anzahl von Kanten in einer Paarung von ${}G$.

Definition:Paarungsbedingung

Es sei ${}G$ ein bipartiter Graph mit einer Bipartition ${}V=A\uplus B$ und sei ${}C\subseteq A$. Man sagt, dass ${}C$ die Paarungsbedingung erfüllt, wenn für jede Teilmenge ${}S\subseteq C$ die Beziehung ${}{\#\left(S\right)}\leq {\#\left(N(S)\right)}$ gilt.

Definition:Alternierender Weg

Es sei ${}G=(V,E)$ ein Graph und ${}P\subseteq E$ eine Paarung. Man nennt einen Weg in ${}G$ alternierend (bezüglich der gegebenen Paarung), wenn er abwechselnd Kanten aus ${}P$ und aus ${}E\setminus P$ besitzt.

Definition:Knotenüberdeckung

Es sei ${}G=(V,E)$ ein Graph. Eine Teilmenge ${}W\subseteq V$ heißt Knotenüberdeckung von ${}G$, wenn jede Kante mindestens einen Knoten aus ${}W$ trifft.

Definition:Minimale Knotenüberdeckung

Es sei ${}G=(V,E)$ ein Graph. Eine Knotenüberdeckung ${}W\subseteq V$ von ${}G$ heißt minimal, wenn ${}W\setminus \{w\}$ zu jedem ${}w\in W$ keine Knotenüberdeckung ist.

Definition:Optimale Knotenüberdeckung

Es sei ${}G=(V,E)$ ein Graph. Eine Knotenüberdeckung ${}W\subseteq V$ von ${}G$ heißt optimal, wenn es keine Knotenüberdeckung von ${}G$ mit weniger als ${}{\#\left(W\right)}$ Elementen gibt.

Definition:Knotenüberdeckungszahl

Es sei ${}G=(V,E)$ ein Graph. Die minimale Anzahl von Knoten in einer Knotenüberdeckung von ${}G$ heißt Knotenüberdeckungszahl von ${}G$.

Definition:Hamiltonkreis

Ein Kreis in einem Graphen ${}(V,E)$ heißt Hamiltonkreis, wenn in ihm jeder Knotenpunkt vorkommt.

Definition:Hamiltonscher Graph

Ein Graph ${}(V,E)$ heißt hamiltonsch, wenn es in ihm einen Hamiltonkreis gibt.

Definition:Eulerscher Kantenzug

Es sei ${}G=(V,E)$ ein Graph. Ein Kantenzug ${}e_{1},\ldots ,e_{m}$ heißt eulersch, wenn in ihm jede Kante aus ${}E$ genau einmal vorkommt.

Definition:Eulerscher Graph

Ein Graph ${}G$ heißt eulersch, wenn in ihm ein geschlossener Eulerzug existiert.

Definition:Kantendisjunkte Untergraphen

Zwei Untergraphen ${}H_{1}=(V_{1},E_{1})\subseteq G$ und ${}H_{2}=(V_{2},E_{2})\subseteq G$ in einem Graphen ${}G=(V,E)$ heißen kantendisjunkt, wenn ${}E_{1}\cap E_{2}=\emptyset$ ist.

Definition:Färbung

Es sei ${}(V,E)$ ein Graph. Eine Abbildung

$f\colon V\longrightarrow B$

in eine Menge ${}B$ heißt Färbung des Graphen.

Definition:Zulässige Färbung

Es sei ${}(V,E)$ ein Graph. Eine Färbung

$f\colon V\longrightarrow B$

heißt zulässig, wenn benachbarte Knotenpunkte stets eine verschiedene Farbe bekommen.

Definition:Chromatische Zahl

Zu einem Graphen ${}G=(V,E)$ nennt man die minimale Anzahl an Farben, die man für eine zulässige Färbung benötigt, die chromatische Zahl des Graphen. Sie wird mit ${}\chi (G)$ bezeichnet.

Definition:Chromatisches Polynom

Zu einem Graphen ${}G=(V,E)$ versteht man unter dem chromatischen Polynom ${}P_{G}$ die Funktion, die durch

${}P_{G}\left(k\right)={\#{\left\{f:V\rightarrow \{1,\ldots ,k\}\mid f{\text{ zulässige Färbung}}\right\}}}\,$

gegeben ist.

Definition:Geometrische Realisierung eines Graphen

Es sei ${}G=(V,E)$ ein Graph. Eine (überschneidungsfreie) geometrische Realisierung von ${}G$ im ${}\mathbb {R} ^{d}$ besteht aus folgenden Daten.

1. Eine injektive Abbildung

   $V\longrightarrow \mathbb {R} ^{d},\,v\longmapsto P_{v},$

   zu jedem Knotenpunkt ${}v\in V$ gibt es also einen Punkt ${}P_{v}\in \mathbb {R} ^{d}$ und verschiedene Knotenpunkte besitzen verschiedene Realisierungen ${}P_{v}$.

2. Zu jeder Kante ${}L=\{u,v\}\in E$ eine injektive stetige Abbildung

   $\varphi _{L}\colon [0,1]\longrightarrow \mathbb {R} ^{d}$

   mit ${}\varphi _{L}(0)=P_{u}$ und ${}\varphi _{L}(1)=P_{v}$.

3. Für verschiedene Kanten ${}L\neq L'$ ist

   ${}\varphi _{L}(]0,1[)\cap \varphi _{L'}(]0,1[)=\emptyset \,.$

Definition:Planarer Graph

Ein Graph heißt planar, wenn er eine geometrische Realisierung im ${}\mathbb {R} ^{2}$ besitzt.