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$, genannt Restgraph, 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 Bildgraphenstruktur 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=(V,E)$  heißt perfekt, wenn die Kanten der Paarung jeden Knoten des Graphen abdecken.

Definition:Maximale Paarung

Eine Paarung  ${}P\subseteq E$  in einem Graphen  ${}G=(V,E)$  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.