How to theoretically compute upper bound for expected number of * edges in a random connected graph. And also write a program to estimate f(n) for * given value of n * Description: Details of theoretical computation of N is given in RandomGraphs

Input: n= 100,200,300,400,500,600,700,800,900,1000
 *  Output: 1685.261890, 3509.153216, 5385.369357, 7295.565304, 9231.028406,
 *  11186.627021 , 13158.970334, 15145.648353, 17144.859130, 19155.203993
 * 
 *  Visible data fields:
 *  Double X, Y, y , Z,F,K; Integer num
 *
 *  Visible methods:
 *  -----------------
 *  UF,Find,Count, connected, union, validate and main method execution.
 *
 *
 *   Remarks
 *   --------
 *  Theoretical upper bound of expected number of edges is Computed and attached 
 *  as RandomGraphs.pdf
 *  Theoretical upper bound after computing : X >= NlogN + ( 10*N*Pi* by sqrt(6))
 *
 *  OUTPUT on EVE: Script done, file is vignan-0981437-1.txt
 *  -------------
 *************************************************************************/

import static java.lang.Math.log;
import java.util.Scanner;

public class comN {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        
      double X, Y; 
      Scanner s = new Scanner(System.in);
      System.out.print("Enter a value for N vertices ");
      int num = s.nextInt();
      
      double y= 22/7;
      double z= Math.sqrt(6);
      double F;
      double K;
      
      
      Y = num * log(num);
      
      F = 10 * num;
      
      K = F * y;
      
      X = (Y + (F * y)/z);
      
      System.out.printf("\nExpected number of Edges to connect with N vertices is gretaer than or Equal to: %f", +X);
      
    }
    
}


import java.util.Scanner;

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author vignan
 */

public class UF {

    private int[] parent;  // parent[i] = parent of i
    private byte[] rank;   // rank[i] = rank of subtree rooted at i (never more than 31)
    private int count;     // number of components

    public UF(int N) {
        if (N < 0) throw new IllegalArgumentException();
        count = N;
        parent = new int[N];
        rank = new byte[N];
        for (int i = 0; i < N; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }


    public int find(int p) {
        validate(p);
        while (p != parent[p]) {
            parent[p] = parent[parent[p]];    // path compression by halving
            p = parent[p];
        }
        return p;
    }


    public int count() {
        return count;
    }
  

    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }
  

    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) return;

        // make root of smaller rank point to root of larger rank
        if      (rank[rootP] < rank[rootQ]) parent[rootP] = rootQ;
        else if (rank[rootP] > rank[rootQ]) parent[rootQ] = rootP;
        else {
            parent[rootQ] = rootP;
            rank[rootP]++;
        }
        count--;
    }

    // validate that p is a valid index
    private void validate(int p) {
        int N = parent.length;
        if (p < 0 || p >= N) {
            throw new IndexOutOfBoundsException("index " + p + " is not between 0 and " + (N-1));  
        }
    }


    public static void main(String[] args) {
        System.out.println("please enter number of integers");
        Scanner scan = new Scanner( System.in );   
        int N =  scan.nextInt();
        UF uf = new UF(N);
       
        while (!scan.hasNext()) {
            System.out.println("please enter integers pairs"); 
            Scanner scan1 = new Scanner( System.in );   
            int p = scan1.nextInt();
            int q = scan1.nextInt();
            if (uf.connected(p, q)) continue;
            uf.union(p, q);
            System.out.println(p + " " + q);
        }
        System.out.println(uf.count() + "These are the number of connected components");
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *