Algorithmische Probleme auf Grapfen

Question 1

Entscheidungsproblematik

Answer 1

Entscheiden, ob:

• G zusammenhängend ist
• G azyklisch ist
• G einen Hamiltonischen Zyklus besitzt, d.h. einen Zyklus der Länge Betrag(V), also über alle Knoten
• G einen Eulerschen Weg besitzt, d.h. eine Kantenfolge, in der jede Kante genau einmal verwendet wird und deren Anfangs- und Endknoten gleich sind

Question 2

Färbungsproblem

Answer 2

Man entscheide zu vorgegebener Zahl k∈N, ob es eine Knotenmarkierung m: V→{1,2,…,k} so gibt, dass für alle (v,w)∈E gilt: m(v)≠m(w)

Question 3

Cliquenproblem

Answer 3

Man entscheide für ungerichtete Graphen G zu gegebener Zahl k∈N, ob es einen Teilgraphen G‘ von G mit k Knoten gibt, dessen Knoten alle paarweise durch Kanten verbunden sind

Question 4

Kürzeste und längste Wege

Answer 4

Gegeben sei ein kantenbewerteter (ungerichteter) Graph. Man suche dabei zu zwei Knoten:

• den kürzesten Weg
• den längsten Weg
  -> Kantenmarkierung

Question 5

Matching-Problem

Answer 5

Eine Teilmenge ( M⊆E) der Kanten heißt Matching, wenn jeder der Knoten von V zu höchstens einer Kante M gehört.
Gesucht ist dabei die Teilmenge M mit größtmöglicher Kantenzahl, die die geforderte Eigenschaft erfüllt
-> maximales Matching