Grundlagen

Definition Graph

Ein schlichter Graph ist ein Paar $G=\left(E,K\right)$, wobei $E=\left\{ v_{1},\ldots,v_{n}\right\}$ eine endliche nicht leere Menge von Ecken und $K\subseteq\left\{ \left\{ v_{i},v_{j}\right\} \vert i\neq j\right\}$ eine Menge von Kanten ist.

Ein Graph (manchmal auch ``Multipgraph'' genannt) erlaubt zusätzlich Schleifen (d.h. $\left\{ v_{i},v_{i}\right\}$) und auch Mehrfachkanten (d.h.

$\left\{ v_{i},v_{j}\right\} _{n}$ hat eine Vielfachheit von $n$) mit einer gewissen Vielfachheit.

• $G$ schlicht und $\left\vert E\right\vert=n\Rightarrow\left\vert k\right\vert\leq\left({{n\atop 2}}\right)$
• $V_{n}=$ vollständiger (schlichter) Graph. D.h. das alle Ecken über kanten mit jeder anderen Ecke verbunden sind.
  • $V_{2n+1}$ ist eulersch
  • $V_{n}$ ist $\left(n-1\right)$-regulär
  • $V_{n}$ ist mit $n\geq5$ nicht plättbar
• Hyperwürfel
  • der 0-dimensionale Hyperwürfel hat eine Ecke, und keine Kante
  • jeder Hyperwürfel ist hamiltonisch
  • Hat der $d$-dimensionale Hyperwürfel $\left(E,K\right)$ die Ecken $v_{1},\ldots,v_{2^{d}}$, so hat der $\left(d+1\right)$-dimensionale Hyperwürfel die Ecken $w_{1},\ldots,w_{2^{d}},w'_{1},\ldots,w'_{2^{d}}$ und die Kanten
    

    $${\scriptstyle \left\{ \left\{ w_{i},w_{j}\right\} ,\left\{ w_{i},w_{j}\right\} \vert i\neq j\wedge\left\{ v_{i},v_{j}\right\} \in K\right\} }$$

    $${\scriptstyle \cup\left\{ \left\{ w_{i},w'_{i}\right\} \vert 1\leq i\leq2^{d}\right\} }$$

    
    

  • ein $d$-dimensionaler Hyperwürfel ist $d$-regulär
  • ein $2n$-dimensionaler Hyperwürfel ist ist eulersch

Grad & Gradfolge

Sei $G=\left(E,K\right)$ ein Graph mit $E=\left\{ v_{1},\ldots,v_{n}\right\}$. Der Grad der Ecke $v$ ist

$$\deg\left(v\right)=\left\vert\left\{ z\in G\vert v\in z\right\} \right\vert$$

Schleifen müssen hierbei doppelt gezählt werden! Der Grad gibt die Anzahl der Kanten an, die $v$ als Ecke haben.

Das $n$-Tupel $\left(\deg\left(v_{1}\right),\ldots\deg\left(v_{n}\right)\right)$ heißt Gradfolge von $G$.

• $\sum_{v\in E}\deg\left(v\right)=2\left\vert K\right\vert$
• Die Anzahl der Ecken mit ungeradem Grad ist gerade
• Es gibt einen schlichten Graphen $G$ mit der Gradfolge $\left(d_{1},\ldots,d_{n}\right)$ mit $d_{1}\geq\ldots\geq d_{n}$ genau dann, wenn es einen Graphen mit der Gradfolge $\left(d_{2}-1,\ldots,d_{d_{1}+1}-1,d_{d_{1}+2},\ldots,d_{n}\right)$ gibt.

Regulär

Der Graph $G=\left(E,K\right)$ heißt $k$-regulär, falls alle Ecken von G den selben Grad $k$ haben.

• $V_{n}$ ist $\left(n-1\right)$-regulär