Übung Grundbegriffe der Graphentheorie 2

Aus ProgrammingWiki

Wechseln zu: Navigation, Suche

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

S3anbrem Graph34.gif
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!

Persönliche Werkzeuge