This is a java program to check graph construction is possible or not using given degree sequence. If the sum of degree is even graph construction is possible, not otherwise.
Here is the source code of the Java Program to Check if any Graph is Possible to be Constructed for a Given Degree Sequence. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
package com.sanfoundry.combinatorial; import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class CheckGraphConstuction { public static Integer sum(List<Integer> list) { Integer sum = 0; for (Integer integer : list) { sum += integer; } return sum; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("Enter the number of vertices: "); Integer n = sc.nextInt(); System.out .println("Enter the Degree Sequence: <Degree sequence is always in non-increasing order>"); List<Integer> sequence = new ArrayList<Integer>(); while (n > 0) { sequence.add(sc.nextInt()); n--; } System.out.println(sequence.toString()); if (sum(sequence) % 2 == 0) { System.out .println("Graph can be constructed using the given sequence G=(" + sequence.size() + ", " + (sum(sequence) / 2) + ")."); } sc.close(); } }
Output:
$ javac CheckGraphConstuction.java $ java CheckGraphConstuction Enter the number of vertices: 7 Enter the Degree Sequence: <Degree sequence is always in non-increasing order> 5 3 3 2 2 1 0 [5, 3, 3, 2, 2, 1, 0] Graph can be constructed using the given sequence G=(7, 8). Enter the number of vertices: 3 Enter the Degree Sequence: <Degree sequence is always in non-increasing order> 3 3 1 [3, 3, 1] no soultion exists.
Related posts:
Java Program to Implement Borwein Algorithm
Guava CharMatcher
Automatic Property Expansion with Spring Boot
Java Program to Implement LinkedHashSet API
Java Program to Implement Queue using Two Stacks
Java Program to Implement Min Hash
Guide to Mustache with Spring Boot
Tiêu chuẩn coding trong Java (Coding Standards)
Java Program to Permute All Letters of an Input String
Count Occurrences of a Char in a String
Guide to the Fork/Join Framework in Java
Java Program to Implement LinkedTransferQueue API
Java Program to Check Whether a Directed Graph Contains a Eulerian Path
Spring Boot - Building RESTful Web Services
Introduction to the Java NIO2 File API
Java Program to Perform Searching in a 2-Dimension K-D Tree
Introduction to Netflix Archaius with Spring Cloud
Spring Web Annotations
Java Program to Implement VList
Spring Boot - Admin Client
Apache Camel with Spring Boot
Java Program to Implement Sorting of Less than 100 Numbers in O(n) Complexity
Send email with SMTPS (eg. Google GMail)
MyBatis with Spring
Using Spring ResponseEntity to Manipulate the HTTP Response
Java – Combine Multiple Collections
Java Program to Implement Extended Euclid Algorithm
Spring Boot - Sending Email
Add Multiple Items to an Java ArrayList
Java Program to Check whether Directed Graph is Connected using DFS
So sánh ArrayList và LinkedList trong Java
Receive email using IMAP