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 Multi-Threaded Version of Binary Search Tree
Introduction to Spring Boot CLI
OAuth2.0 and Dynamic Client Registration
Apache Commons Collections SetUtils
The Java 8 Stream API Tutorial
Java Program to Implement the Bin Packing Algorithm
Spring Boot - Tomcat Port Number
Spring Security Remember Me
Java Program to subtract two large numbers using Linked Lists
Configuring a DataSource Programmatically in Spring Boot
Mệnh đề Switch-case trong java
How to Read HTTP Headers in Spring REST Controllers
Custom HTTP Header with the HttpClient
StringBuilder vs StringBuffer in Java
Java Program to Implement Queue using Two Stacks
Jackson Unmarshalling JSON with Unknown Properties
HttpClient 4 – Send Custom Cookie
Hướng dẫn sử dụng biểu thức chính quy (Regular Expression) trong Java
Spring Boot - Web Socket
An Intro to Spring Cloud Task
Java Program to Implement Sorted Circular Doubly Linked List
Java Program to Use Above Below Primitive to Test Whether Two Lines Intersect
Basic Authentication with the RestTemplate
Java Program to Perform Partition of an Integer in All Possible Ways
Java Program to Perform Quick Sort on Large Number of Elements
The Guide to RestTemplate
Tạo ứng dụng Java RESTful Client không sử dụng 3rd party libraries
Create a Custom Exception in Java
Logging in Spring Boot
Java Program to Implement Treap
Java Program to Implement Doubly Linked List
Java Program to Perform Left Rotation on a Binary Search Tree