# Hausaufgaben zu Graphen

[TOC]

## Adjazenzmatrix

Die umgangssprachliche Vorschrift ist ein Algorithmus, da sie auch eine endliche Anzahl von wohldefinierten Handlungsschritten hat.

## Wege-Probleme

function checkConnection(u, v, adjacencymatrix)
    list visited
    list pot_adjacents
    bool found
    stack connected
    connected.push(u)
    while not found and not connected.empty
        cur_vert = connected.pop()
        pot_adjacents = adjacencymatrix[cur_vert]
        if pot_adjacents[v]
            found = True
            continue
        for j, i in enumerate(pot_adjacents)
            if i and not j in visited
                connected.push(i)
        visited.append(cur_vert)
        
    return found
   
print(checkConnection(u, v, Adjazenzmatrix))

*Erklärung:*

*Wir gehen von einer gegebenen Adjazenzmatrix und den Knoten u & v, die auf eine Verbindung untersucht werden sollen, aus. Während wir die Knoten untersuchen, merken wir uns, welche schon bis zum Ende überprüft wurden. Wir fangen an bei u und gucken ob er direkt mit v verbunden ist. Wenn nicht, schauen wir ob die Knoten die mit u verbunden sind mit v verbunden sind, dann schauen wir uns die Knoten an, die mit den Knoten, die mit u verbunden sind an und immer so weiter, bis wir entweder v finden oder alle durch einen Weg mit u verbundenen Knoten untersucht haben.*

## Kantenanzahl in Graphen

**1.**

*Herleitung über das Ergebnis aus **2**:*

*Bei einem ungerichteten Graphen, kann, nicht so wie beim gerichteten, kein Knoten mit sich selbst eine Kante bilden. Daher wissen wir, dass beim ungerichteten Graphen für jeden Knoten eine Kante weniger als beim gerichteten gibt. Zusätzlich gibt es zwischen zwei Knoten nur eine mögliche Kante und nicht zwei, wie beim gerichteten Graphen, da die Richtung keine Rolle mehr spielt. Also muss noch durch zwei geteilt werden.*

$f: \mathbb{N} \rightarrow \mathbb{N}; n \rightarrow \frac{n^2-n}{2}$
***

*Herleitung über Binomialkoeffizienten:*

$$
\begin{align*}
\binom{n}{k} &= \frac{n!}{k!(n-k)!}\\\\
\binom{n}{2} &= \frac{n!}{2!(n-2)!}\\
\Leftrightarrow\binom{n}{2} &= \frac{n!}{2!(n-2)!}\\
\Leftrightarrow\binom{n}{2} &= \frac{n!}{2!(n-2)!}\cdot \frac{n(n-1)}{n(n-1)}\\
\Leftrightarrow\binom{n}{2} &= \frac{n!\cdot n(n-1)}{2!\cdot n!}\\
\Leftrightarrow\binom{n}{2} &= \frac{n(n-1)}{2}\\
\Leftrightarrow\binom{n}{2} &= \frac{n^2-n}{2}\\
\end{align*}\\
$$

$\large \Rightarrow f: \mathbb{N} \rightarrow \mathbb{N}; n \rightarrow \frac{n^2-n}{2}$

**2.**
*Herleitung:*

*Jeder Knoten kann eine Kante zu jedem anderen Knoten, inklusive ihm selber, haben. Dass heißt, dass bei $n$ Knoten, jeder Knoten $n$ Kanten hat.*

$f: \mathbb{N} \rightarrow \mathbb{N}; n \rightarrow n^2$