Gerichteter Graph: Eingangs- und Ausgangsgrad von Knoten

Question

die Frage lautet:  Was kann man über den größten und den kleinsten Ausgangsgrad der Knoten eines gerichteten Graphen mit 4 Knoten sagen, bei dem der Knoten mit dem höchsten Eingangsgrad den Eingangsgrad 3 hat?

Ich komme mit der Frage nicht ganz zurecht, da man den Graphen ja beliebig zeichnen kann und auch nicht gesagt ist ob Schleifen vorkommen oder nicht. Wäre über jede Hilfe sehr Dankbar.

Answer 1

> und auch nicht gesagt ist ob Schleifen vorkommen oder nicht.

Laut Volkmann können Schleifen und auch parallele Kanten vorkommen. Einen gerichteten  Graphen ohne Schleifen nennt er Multidigraph. Multidigraphen ohne parallele Kanten nennt er schlichte gerichtete Graphen.

Schaue in deine Unterlagen ob das bei dir anders geregelt ist.

> bei dem der Knoten mit dem höchsten Eingangsgrad den Eingangsgrad 3 hat.

Der minimale Ausgangsgrad ist 0.

Ohne Schleifen und parallele Kanten ist der maximale Ausgangsgrad 3, nämlich wenn der Graph vollständig ist.

Parallele Kanten erhöhen den maximalen Ausgangsgrad auf 9, Schleifen auf 4. Lässt man beides zu, dann ist der maximale Ausgangsgrad 12.