Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Nebenfächer » mathematik » 1. Allgemeines zu Graphen

Inhaltsverzeichnis

Ich hatte meine vier Blätter wie folg beschriftet: 2 mit allen Sätzen/ Lemmas und Korollaren die im VL Skript oder der Übung bewiesen wurden. 1 Blatt mit allen Algos abgeschrieben aus dem Skript. 1 Blatt mit generellen Infos und einer Übersicht mit dem Unterschieden der Algorithmen der VL.

Wenn ich die Klausur nochmal schreiben würde, würde ich auf das Blatt zu den Algos verzichten und statdessen zu jedem Algorithmus der drankommen könnte (Bellman-Ford, Edmonds-Karp, Min-Flow-Klein, Prim, Dejkstra, etc.) den groben Ablauf (Tabelle oder am Graphen) draufzeichnen.

1. Allgemeines zu Graphen

1.1.

1.1.1.

Aus gegebenen Graphen unabhängige Kanten-/ Knotenmenge ablesen und angeben

1.1.2.

2 Graphen zeichnen die bestimmte Bedeckende Kanten-/ Knotenmenge hattten ($tau(G)=3,rho(G)=2$)

1.2.

Ein Satz zu Hamiltonkreiesen war gegeben, mit dessen Hilfe sollte ein zweiter Satz bewiesen werden. Beide Sätze kamen *nicht* in der Vorlesung vor.

2. Bellman-Ford

Auf gegebenen Graphen (4 Knoten) Bellman Ford Algo aus VL ausführen. In jeder Iteration eine Tabelle ausfüllen. Anzahl an Iterationen ($abs(V)-1$) war sogar gegeben

3. Ford-Fulkerson

Aus gegebenen Graphen (6 Knoten) Ford-Fulkerson Algo aus VL ausführen. In jeder Iteration den Weg P, $Delta(P)$ und Residualnetz angeben

4. Modellierung

Farm die Pflanzen anbaut modelieren und Ertrag maximieren. Dabei waren drei Sorten an Pflanzen (Wassermelonen, Trauben und Kartoffeln) gegeben mit unterschedlichem Wasserverbrauch je Fläche und Ertrag je Fläche. Zusätzlich Drei Felder mit Fläche und verfügbaren Wasser gegeben. Zusatz war das auf jeder Farm der gleche Anteil an Fläche bewirtschaftet werden sollte.

5. Simplex

Zu gegebenen linearen Optimierungsproblem den Algo aus der VL durchführen

6. Dualität

6.1.

Zu 3 gegebenen min/ max Problemen das jeweilige duale Problem angeben

6.2.

Ein Ungleichungssystem mit Nebenbedigungen ugs_1 war gegeben. Zu beweisen war, dass ein lineares Problem lp1 (auch gegeben) genau dann eine optimale Lösung besitzt, wenn das Ungleichungssystem eine Lösungbesitz. Trick hierbei war zu erkennen, das ugs_1 aus lp1 und dem zu lp1 zugehörigen dualen Problem bestand. Dann konnte man über den schwachen Dualitätssatz argumentieren.