Übung Grundbegriffe der Graphentheorie 2
Aus ProgrammingWiki
Sie sollen diese JAVA-Klasse in Netbeans oder Eclipse benutzen. Sie sollen nur richtige Eingaben im Konsole (oben) schreiben :)
Wenn Sie die Fragen haben , probiere ich verschaffen .
Viel Erfolg!
Inhaltsverzeichnis |
Graphen in Java
Algorithmus von Prim
Der Algorithmus von Prim dient der Berechnung eines minimalen Spannbaumes in einem zusammenhängenden, ungerichteten, kantengewichteten Graphen.
[1]
Java Program to Find MST(Minimum Spanning Tree) using Prim’s Algorithm
Output --> Lösung
Zusätzliche Informationen
[[https://www.youtube.com/watch?v=Pn874kEc3IA ]] [[2]]
Create a Balanced Binary Tree of the Incoming Data
2. MOEGLICHKEIT
Output --> Loesung
Implement Binary Tree
Output --> Loesungen
Find Number of Spanning Trees in a Complete Bipartite Graph
1. Import Scanner
2. Implementieren Sie eine Klasse NumOfSpanningBipartite,die folgende Anforderungen erfuellt:
- Die integer Zahlen "firstSetSize" und "secondSetSize" werden werden im Methode als Parameter erwartet und in privaten Attributen abgespeichert.
- return (this.firstSetSize^(this.secondSetSize - 1)) *(this.secondSetSize ^ (this.firstSetSize -1));
3. Implementieren Sie eine main- Klasse nur mit String[args] Parameter
- Deklarieren Sie m und n als Zahlvariable(int)
- Benutzen Sie die Scanner Prozedure.
- Drucken Sie " Enter the size of the bipartite graph(m and n)
- Benutzen Sie eine Methode Scanner fuer m und n (next...())
- Erzeugen Sie ein neues Objekt bipartite.
- Benutzen Sie System.out.println(...+bipartite.numerOfSpanningTree(m,n)))
- Schliessen Sie Scanner Methode.
OUTPUT:
Ich hoffe, dass ganze Gruppe damit zurechtkommen :D Aber machen Sie keine Sorgen, die Loesungen werde ich nach der Unterrichte schreiben.Wenn jemand eine Frage habt, probiere ich zu helfen! :}
Aufgaben
Aufgabe1
Wieviele Zusammenhangskomponenten hat der Graph?
Ist der Graph bipartit?
dG(x,y) =?
dG(x,z)
Wieviel Kreise gibt es im Graphen ?
Wieviele Wege gibt es von x nach y?
Übung zu Gozinto-Graphen
Zur Produktion eines Endproduktes A werden 4 Teile vom Typ B, 2 Teile Typ C, 3Teile Typ D und 1Teil vom Typ E benötigt. Typ E fließt mit je 1Teil auch noch in die Produktion von D und C ein. Ein weiterer Bautyp F fließt zu je 2Stk in die Produktion von C und mit je 1Stk in die Produktion von B ein.
1.Zeichne einen Gozinto-Graphen zu dem beschriebenen Sachverhalt.
2.Wir erhalten einen Auftrag und sollen 150A, 400B, 50C, 100D, 200E und 300F
bereitstellen. Ermitteln sie den Gesamtbedarf für alle Teile der Produktionskette!
LÖSUNG
Direktmatrix ------ und ------ Einheitsmatrix
0| 1| 0| 2| 0| 0 | 1| 0| 0| 0| 0| 0 0| 0| 0| 0| 0| 4 | 0| 1| 0| 0| 0| 0 0| 0| 0| 1| 1| 1 | 0| 0| 1| 0| 0| 0 0| 0| 0| 0| 0| 2 | 0| 0| 0| 1| 0| 0 0| 0| 0| 0| 0| 3 | 0| 0| 0| 0| 1| 0 0| 0| 0| 0| 0| 0 | 0| 0| 0| 0| 0| 1
Einheitsmatrix - Direktmatrix
1|-1| 0| 2| 0| 0 0| 1| 0| 0| 0|-4 +4*Zeile6 0| 0| 1|-1|-1|-1 +Zeile6 0| 0| 0| 1| 0|-2 +2*Zeile6 0| 0| 0| 0| 1|-3 +3*Zeile6 0| 0| 0| 0| 0| 1
1|-1| 0| 2| 0| 0 +2*Zeile4 | +Zeile2 0| 1| 0| 0| 0| 4 0| 0| 1|-1|-1| 1 0| 0| 0| 1| 0| 2 +Zeile5 |+Zeile4 0| 0| 0| 0| 1| 3 0| 0| 0| 0| 0| 1
Ergebnis der Invertierung
1| 1| 0| 2| 0| 8 0| 1| 0| 0| 0| 4 0| 0| 1| 1| 1| 6 0| 0| 0| 1| 0| 2 0| 0| 0| 0| 1| 3 0| 0| 0| 0| 0| 1
Multiplikation mit Primärbedarfvektor
(1*300)+(1*400)+(0*200)+(2*50)+(0*100)+(8*150) = 2000
0+400+0+0+0+600 = 1000
0+0+200+50+100+900 = 1250
0+0+0+50+0+300 = 350
0+0+0+0+100+450 = 550
0+0+0+0+0+150 = 150
Übung zu Bipartität
- Aufgabe: Erstelle ein Programm welches testet ob ein zusammenhängender Graph bipartit ist oder nicht. Orientiere dich dabei an dem in der Vorlesung vorgestellten Algorithmus im Abschnitt: Konstruktion einer Zerlegung von V in S und T!
- Zusatzaufgabe: Schreibe das Programm so um, dass es auch für nicht zusammenhängende Graphen funktioniert.
- Zusatzaufgabe: Führe eine empirische Effizienzanalyse mit dem Testprogramm durch.
Hilfestellung zur Aufgabenstellung findest du in dem folgenden Code für ein funktionierendes Testprogramm, welches allerdings noch einige Optimierungsmöglichkeiten bietet!
- Zusatzaufgabe: Hat das vorgestellte Programm linearen Aufwand? Begründe deine Antwort!