Bei der Zielfindung in einem Graphen kann man folgende Grundtypen
unterscheiden:
- Kanten auswählen:
- Shortest Path:
- Travelling Salesman:
(Jeden Knoten besuchen)
- Chinese Postman:
(Jeden Knoten besuchen)
- Spanning Tree:
- Knoten auswählen:
- größte Clique finden:
- Independent Set:
- Zentrum finden:
- Kanten Werte zuordnen
- Maximum Flow: In einem Graphen versucht man unter Einhaltung von
Kantenkapazitäten möglichst viele Einheiten (Güter etc.) von einer Quelle
zu einer Senke fließen zu lassen.
- Minimum Cost Flow: Hier wird versucht, bestimmte Nachfragen in Knoten
durch Angebote in anderen Knoten durch einen Fluß zu befriedigen und die
dabei entstehenden Kosten minimal zu halten.
- Knoten Werte zuwiesen:
- Coloring (Färbung):
- Scheduling: