Übung Grundbegriffe der Graphentheorie 2

Aus ProgrammingWiki

Archivierte Version vom 2015-11-04T12:10:49+00:00. Aktuelle Version

Inhaltsverzeichnis

1 '''Graphen in Java'''
2 ''' Aufgaben'''
- 2.1 '''Aufgabe1'''
- 2.1 Übung zu Gozinto-Graphen

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!

Graphen in Java

Algorithmus

https://www.youtube.com/embed/6hfOvs8pY1k

Algorithmus von Prim

Der Algorithmus von Prim dient der Berechnung eines minimalen Spannbaumes in einem zusammenhängenden, ungerichteten, kantengewichteten Graphen.
https://upload.wikimedia.org/wikipedia/commons/archive/b/b1/20150611221338%21MAZE_30x20_Prim.ogv

Java Program to Find MST(Minimum Spanning Tree) using Prim’s Algorithm

import java.util.InputMismatchException;
import java.util.Scanner;
 
public class Prims
{
    private final boolean unsettled[];
    private final boolean settled[];
    private final int numberofvertices;
    private final int adjacencyMatrix[][];
    private final int key[];
    public static final int INFINITE = 999;
    private final int parent[];
 
    public Prims(int numberofvertices)
    {
        this.numberofvertices = numberofvertices;
        unsettled = new boolean[numberofvertices + 1];
        settled = new boolean[numberofvertices + 1];
        adjacencyMatrix = new int[numberofvertices + 1][numberofvertices + 1];
        key = new int[numberofvertices + 1];
        parent = new int[numberofvertices + 1];
    }
 
    public int getUnsettledCount(boolean unsettled[])
    {
        int count = 0;
        for (int index = 0; index < unsettled.length; index++)
        {
            if (unsettled[index])
            {
                count++;
            }
        }
        return count;
    }
 
    public void primsAlgorithm(int adjacencyMatrix[][])
    {
        int evaluationVertex;
        for (int source = 1; source <= numberofvertices; source++)
        {
            for (int destination = 1; destination <= numberofvertices; destination++)
            {
                this.adjacencyMatrix[source][destination] = adjacencyMatrix[source][destination];
            }
        }
 
        for (int index = 1; index <= numberofvertices; index++)
        {
            key[index] = INFINITE;
        }
        key[1] = 0;
        unsettled[1] = true;
        parent[1] = 1;
 
        while (getUnsettledCount(unsettled) != 0)
        {
            evaluationVertex = getMimumKeyVertexFromUnsettled(unsettled);
            unsettled[evaluationVertex] = false;
            settled[evaluationVertex] = true;
            evaluateNeighbours(evaluationVertex);
        }
    } 
 
    private int getMimumKeyVertexFromUnsettled(boolean[] unsettled2)
    {
        int min = Integer.MAX_VALUE;
        int node = 0;
        for (int vertex = 1; vertex <= numberofvertices; vertex++)
        {
            if (unsettled[vertex] == true && key[vertex] < min)
            {
                node = vertex;
                min = key[vertex];
            }
        }
        return node;
    }
 
    public void evaluateNeighbours(int evaluationVertex)
    {
 
        for (int destinationvertex = 1; destinationvertex <= numberofvertices; destinationvertex++)
        {
            if (settled[destinationvertex] == false)
            {
                if (adjacencyMatrix[evaluationVertex][destinationvertex] != INFINITE)
                {
                    if (adjacencyMatrix[evaluationVertex][destinationvertex] < key[destinationvertex])
                    {
                        key[destinationvertex] = adjacencyMatrix[evaluationVertex][destinationvertex];
                        parent[destinationvertex] = evaluationVertex;
                    }
                    unsettled[destinationvertex] = true;
                }
            }
        }
    }
 
    public void printMST()
    {
        System.out.println("SOURCE  : DESTINATION = WEIGHT");
        for (int vertex = 2; vertex <= numberofvertices; vertex++)
        {
            System.out.println(parent[vertex] + "\t:\t" + vertex +"\t=\t"+ adjacencyMatrix[parent[vertex]][vertex]);
        }
    }
 
    public static void main(String... arg)
    {
        int adjacency_matrix[][];
        int number_of_vertices;
        Scanner scan = new Scanner(System.in);
 
        try
        {
            System.out.println("Enter the number of vertices");
            number_of_vertices = scan.nextInt();
            adjacency_matrix = new int[number_of_vertices + 1][number_of_vertices + 1];
 
            System.out.println("Enter the Weighted Matrix for the graph");
            for (int i = 1; i <= number_of_vertices; i++)
            {
                for (int j = 1; j <= number_of_vertices; j++)
                {
                    adjacency_matrix[i][j] = scan.nextInt();
                    if (i == j)
                    {
                        adjacency_matrix[i][j] = 0;
                        continue;
                    }
                    if (adjacency_matrix[i][j] == 0)
                    {
                        adjacency_matrix[i][j] = INFINITE;
                    }
                }
            }
 
            Prims prims = new Prims(number_of_vertices);
            prims.primsAlgorithm(adjacency_matrix);
            prims.printMST();
 
        } catch (InputMismatchException inputMismatch)
        {
            System.out.println("Wrong Input Format");
        }
        scan.close();
    }
}

Output --> Lösung

Zusätzliche Informationen

https://www.youtube.com/watch?v=Pn874kEc3IA https://www.youtube.com/embed/ENWVRcMGDoU

Create a Balanced Binary Tree of the Incoming Data

//This is a java program to insert elements in a Binary Search Tree
import java.util.Scanner;
 
class BSTNode
{
    BSTNode left, right;
    int     data;
 
    public BSTNode()
    {
        left = null;
        right = null;
        data = 0;
    }
 
    public BSTNode(int n)
    {
        left = null;
        right = null;
        data = n;
    }
 
    public void setLeft(BSTNode n)
    {
        left = n;
    }
 
    public void setRight(BSTNode n)
    {
        right = n;
    }
 
    public BSTNode getLeft()
    {
        return left;
    }
 
    public BSTNode getRight()
    {
        return right;
    }
 
    public void setData(int d)
    {
        data = d;
    }
 
    public int getData()
    {
        return data;
    }
}
 
class BSTree
{
    private BSTNode root;
 
    public BSTree()
    {
        root = null;
    }
 
    public boolean isEmpty()
    {
        return root == null;
    }
 
    public void insert(int data)
    {
        root = insert(root, data);
    }
 
    private BSTNode insert(BSTNode node, int data)
    {
        if (node == null)
            node = new BSTNode(data);
        else
        {
            if (data <= node.getData())
                node.left = insert(node.left, data);
            else
                node.right = insert(node.right, data);
        }
        return node;
    }
 
    public void inorder()
    {
        inorder(root);
    }
 
    private void inorder(BSTNode r)
    {
        if (r != null)
        {
            inorder(r.getLeft());
            System.out.print(r.getData() + " ");
            inorder(r.getRight());
        }
    }
 
    public void preorder()
    {
        preorder(root);
    }
 
    private void preorder(BSTNode r)
    {
        if (r != null)
        {
            System.out.print(r.getData() + " ");
            preorder(r.getLeft());
            preorder(r.getRight());
        }
    }
 
    public void postorder()
    {
        postorder(root);
    }
 
    private void postorder(BSTNode r)
    {
        if (r != null)
        {
            postorder(r.getLeft());
            postorder(r.getRight());
            System.out.print(r.getData() + " ");
        }
    }
}
 
public class Insertion_BST
{
    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        BSTree bst = new BSTree();
        System.out.println("Binary Search Tree Insertion Test\n");
        int N = 10;
        for (int i = 0; i < N; i++)
        {
            bst.insert(scan.nextInt());
            System.out.print("\nPost order : ");
            bst.postorder();
            System.out.print("\nPre order  : ");
            bst.preorder();
            System.out.print("\nIn order   : ");
            bst.inorder();
        }
        scan.close();
    }
}

2. MOEGLICHKEIT

//This is a java program to make a self balancing binary tree for the input data
import java.util.Scanner;
 
class SBBSTNodes
{
    SBBSTNodes left, right;
    int        data;
    int        height;
 
    public SBBSTNodes()
    {
        left = null;
        right = null;
        data = 0;
        height = 0;
    }
 
    public SBBSTNodes(int n)
    {
 
        left = null;
        right = null;
        data = n;
        height = 0;
    }
}
 
class SelfBalancingBinarySearchTrees
{
    private SBBSTNodes root;
 
    public SelfBalancingBinarySearchTrees()
    {
        root = null;
    }
 
    public boolean isEmpty()
    {
        return root == null;
    }
 
    public void clear()
    {
        root = null;
    }
 
    public void insert(int data)
    {
        root = insert(data, root);
    }
 
    private int height(SBBSTNodes t)
    {
 
        return t == null ? -1 : t.height;
    }
 
    private int max(int lhs, int rhs)
    {
        return lhs > rhs ? lhs : rhs;
    }
 
    private SBBSTNodes insert(int x, SBBSTNodes t)
    {
        if (t == null)
            t = new SBBSTNodes(x);
        else if (x < t.data)
        {
            t.left = insert(x, t.left);
            if (height(t.left) - height(t.right) == 2)
                if (x < t.left.data)
                    t = rotateWithLeftChild(t);
                else
                    t = doubleWithLeftChild(t);
        } else if (x > t.data)
        {
            t.right = insert(x, t.right);
            if (height(t.right) - height(t.left) == 2)
                if (x > t.right.data)
                    t = rotateWithRightChild(t);
                else
                    t = doubleWithRightChild(t);
        } else
            ;
        t.height = max(height(t.left), height(t.right)) + 1;
        return t;
    }
 
    private SBBSTNodes rotateWithLeftChild(SBBSTNodes k2)
    {
        SBBSTNodes k1 = k2.left;
        k2.left = k1.right;
        k1.right = k2;
        k2.height = max(height(k2.left), height(k2.right)) + 1;
        k1.height = max(height(k1.left), k2.height) + 1;
        return k1;
    }
 
    private SBBSTNodes rotateWithRightChild(SBBSTNodes k1)
    {
        SBBSTNodes k2 = k1.right;
        k1.right = k2.left;
        k2.left = k1;
        k1.height = max(height(k1.left), height(k1.right)) + 1;
        k2.height = max(height(k2.right), k1.height) + 1;
        return k2;
    }
 
    private SBBSTNodes doubleWithLeftChild(SBBSTNodes k3)
    {
        k3.left = rotateWithRightChild(k3.left);
        return rotateWithLeftChild(k3);
    }
 
    private SBBSTNodes doubleWithRightChild(SBBSTNodes k1)
    {
        k1.right = rotateWithLeftChild(k1.right);
        return rotateWithRightChild(k1);
    }
 
    public int countNodes()
    {
        return countNodes(root);
    }
 
    private int countNodes(SBBSTNodes r)
    {
        if (r == null)
            return 0;
        else
        {
            int l = 1;
            l += countNodes(r.left);
            l += countNodes(r.right);
            return l;
        }
    }
 
    public boolean search(int val)
    {
        return search(root, val);
    }
 
    private boolean search(SBBSTNodes r, int val)
    {
        boolean found = false;
        while ((r != null) && !found)
        {
            int rval = r.data;
            if (val < rval)
                r = r.left;
            else if (val > rval)
                r = r.right;
            else
            {
                found = true;
                break;
            }
            found = search(r, val);
        }
        return found;
    }
 
    public void inorder()
    {
        inorder(root);
    }
 
    private void inorder(SBBSTNodes r)
    {
        if (r != null)
        {
            inorder(r.left);
            System.out.print(r.data + " ");
            inorder(r.right);
        }
    }
 
    public void preorder()
    {
 
        preorder(root);
    }
 
    private void preorder(SBBSTNodes r)
    {
        if (r != null)
        {
            System.out.print(r.data + " ");
            preorder(r.left);
            preorder(r.right);
        }
    }
 
    public void postorder()
    {
        postorder(root);
    }
 
    private void postorder(SBBSTNodes r)
    {
        if (r != null)
        {
            postorder(r.left);
            postorder(r.right);
            System.out.print(r.data + " ");
        }
    }
}
 
public class Balanced_B_Tree
{
    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
 
        SelfBalancingBinarySearchTrees sbbst = new SelfBalancingBinarySearchTrees();
        System.out.println("Self Balancing Tree\n");
 
        int N = 10;
        for (int i = 0; i < N; i++)
            sbbst.insert(scan.nextInt());
 
        System.out.println("\nPre-order  :");
        sbbst.preorder();
        System.out.println("\nIn-order   :");
        sbbst.inorder();
        System.out.println("\nPost-order :");
        sbbst.postorder();
        scan.close();
    }
}

Output --> Loesung

Implement Binary Tree

/*
 *  Java Program to Implement Binary Tree
 */
 
 import java.util.Scanner;
 
 /* Class BTNode */
 class BTNode
 {    
     BTNode left, right;
     int data;
 
     /* Constructor */
     public BTNode()
     {
         left = null;
         right = null;
         data = 0;
     }
     /* Constructor */
     public BTNode(int n)
     {
         left = null;
         right = null;
         data = n;
     }
     /* Function to set left node */
     public void setLeft(BTNode n)
     {
         left = n;
     }
     /* Function to set right node */ 
     public void setRight(BTNode n)
     {
         right = n;
     }
     /* Function to get left node */
     public BTNode getLeft()
     {
         return left;
     }
     /* Function to get right node */
     public BTNode getRight()
     {
         return right;
     }
     /* Function to set data to node */
     public void setData(int d)
     {
         data = d;
     }
     /* Function to get data from node */
     public int getData()
     {
         return data;
     }     
 }
 
 /* Class BT */
 class BT
 {
     private BTNode root;
 
     /* Constructor */
     public BT()
     {
         root = null;
     }
     /* Function to check if tree is empty */
     public boolean isEmpty()
     {
         return root == null;
     }
     /* Functions to insert data */
     public void insert(int data)
     {
         root = insert(root, data);
     }
     /* Function to insert data recursively */
     private BTNode insert(BTNode node, int data)
     {
         if (node == null)
             node = new BTNode(data);
         else
         {
             if (node.getRight() == null)
                 node.right = insert(node.right, data);
             else
                 node.left = insert(node.left, data);             
         }
         return node;
     }     
     /* Function to count number of nodes */
     public int countNodes()
     {
         return countNodes(root);
     }
     /* Function to count number of nodes recursively */
     private int countNodes(BTNode r)
     {
         if (r == null)
             return 0;
         else
         {
             int l = 1;
             l += countNodes(r.getLeft());
             l += countNodes(r.getRight());
             return l;
         }
     }
     /* Function to search for an element */
     public boolean search(int val)
     {
         return search(root, val);
     }
     /* Function to search for an element recursively */
     private boolean search(BTNode r, int val)
     {
         if (r.getData() == val)
             return true;
         if (r.getLeft() != null)
             if (search(r.getLeft(), val))
                 return true;
         if (r.getRight() != null)
             if (search(r.getRight(), val))
                 return true;
         return false;         
     }
     /* Function for inorder traversal */
     public void inorder()
     {
         inorder(root);
     }
     private void inorder(BTNode r)
     {
         if (r != null)
         {
             inorder(r.getLeft());
             System.out.print(r.getData() +" ");
             inorder(r.getRight());
         }
     }
     /* Function for preorder traversal */
     public void preorder()
     {
         preorder(root);
     }
     private void preorder(BTNode r)
     {
         if (r != null)
         {
             System.out.print(r.getData() +" ");
             preorder(r.getLeft());             
             preorder(r.getRight());
         }
     }
     /* Function for postorder traversal */
     public void postorder()
     {
         postorder(root);
     }
     private void postorder(BTNode r)
     {
         if (r != null)
         {
             postorder(r.getLeft());             
             postorder(r.getRight());
             System.out.print(r.getData() +" ");
         }
     }     
 }
 
 /* Class BinaryTree */
public class BinaryTree
 {
     public static void main(String[] args)
    {            
        Scanner scan = new Scanner(System.in);
        /* Creating object of BT */
        BT bt = new BT(); 
        /*  Perform tree operations  */
        System.out.println("Binary Tree Test\n");          
        char ch;        
        do    
        {
            System.out.println("\nBinary Tree Operations\n");
            System.out.println("1. insert ");
            System.out.println("2. search");
            System.out.println("3. count nodes");
            System.out.println("4. check empty");
 
            int choice = scan.nextInt();            
            switch (choice)
            {
            case 1 : 
                System.out.println("Enter integer element to insert");
                bt.insert( scan.nextInt() );                     
                break;                          
            case 2 : 
                System.out.println("Enter integer element to search");
                System.out.println("Search result : "+ bt.search( scan.nextInt() ));
                break;                                          
            case 3 : 
                System.out.println("Nodes = "+ bt.countNodes());
                break;     
            case 4 : 
                System.out.println("Empty status = "+ bt.isEmpty());
                break;            
            default : 
                System.out.println("Wrong Entry \n ");
                break;   
            }
            /*  Display tree  */ 
            System.out.print("\nPost order : ");
            bt.postorder();
            System.out.print("\nPre order : ");
            bt.preorder();
            System.out.print("\nIn order : ");
            bt.inorder();
 
            System.out.println("\n\nDo you want to continue (Type y or n) \n");
            ch = scan.next().charAt(0);                        
        } while (ch == 'Y'|| ch == 'y');               
    }
 }

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:

Details

$javac NumOfSpanningBipartite.java

$java NumOfSpanningBipartite

enter the size of the bipartite graph (m and n)
2 2

the number of spanning trees are  9

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!

Direktmatrix

0| 1| 0| 2| 0| 0
0| 0| 0| 0| 0| 4
0| 0| 0| 1| 1| 1
0| 0| 0| 0| 0| 2
0| 0| 0| 0| 0| 3
0| 0| 0| 0| 0| 0

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

Übung Grundbegriffe der Graphentheorie 2

Inhaltsverzeichnis

Graphen in Java

Algorithmus

Algorithmus von Prim

Java Program to Find MST(Minimum Spanning Tree) using Prim’s Algorithm

Create a Balanced Binary Tree of the Incoming Data

Implement Binary Tree

Find Number of Spanning Trees in a Complete Bipartite Graph

Aufgaben

Aufgabe1

Übung zu Gozinto-Graphen

Suche