Induced subgraph Program Plan: Create a package “main”. Add a java class named “Edge” to the package which is used to get the edges from the graph. Add a java class named “Graph” to the package which is used to add and remove vertices, edges. Add a java class named “UnweightedGraph” to the package which is used to store vertices and neighbors. Add a java class named “WeightedGraph” to the package which is used to get the weighted edges and print the edges. Add a java class named “WeightedEdge” to the package which is used to compare edges. Add a java class named “E16” to the package. Import the required packages. Declare the main class. Give the “main ()” method. Declare the string array that contains the names of the city. Declare an integer array that contains the weight. Create an object for unweighted graph. Print the size of the graph, vertex of the graph, index of the vertex “Miami”, and the edges of the graph. Call the function “maxInducedSubgraph ()”. Print the size of the graph, vertex of the graph, index of the vertex “Miami”, and the edges of the graph. Give function definition for “maxInducedSubgraph ()”. Declare required variables Do until the condition “(!Isdone && g.getSize() > 0)” fails. Assign “true” to the variable. Loop from 0 through size. Check the condition “(g.getDegree(i) < k)”. Call the function “remove_Vertex ()”. Assign false to the variable. Break the loop. Return the graph. Function definition for “UnweightedGraphInducedSubgraph ()”. Construct the empty graph. Construct a graph from vertices and edges stored in arrays. Get the vertices and edges. Construct a graph from vertices and edges stored in List. Get the vertices and edges. Construct a graph for integer vertices 0, 1, 2 and edge list. Get the vertices and edges. Construct a graph from integer vertices 0, 1, and edge array. Get the vertices and edges. Give function definition for “remove_Vertex ()”. Check the condition “(vertices.contains(v))”. Get the index. Call the functions “vertices.remove ()”, and “neighbors.remove ()”. Loop to remove the edges. Loop from 0 through size. Check the condition “(list.get(i).v == index)”. If it is true then remove the edge. Else, increment the variable Loop to reassign the labels. Loop from 0 through size. Check the condition “(list.get(i).u >= index)”. If the condition is true then get the edge Check the condtion “(list.get(i).v >= index)”. If the condition is true then get the edge Return “true”. Else, Return “false”.

Question

Want to see the full answer?

Answer 1

Question

Chapter 28, Problem 28.16PE

Program Plan Intro

Induced subgraph

Program Plan:

Create a package “main”.

Add a java class named “Edge” to the package which is used to get the edges from the graph.

Add a java class named “Graph” to the package which is used to add and remove vertices, edges.

Add a java class named “UnweightedGraph” to the package which is used to store vertices and neighbors.

Add a java class named “WeightedGraph” to the package which is used to get the weighted edges and print the edges.

Add a java class named “WeightedEdge” to the package which is used to compare edges.

Add a java class named “E16” to the package.

Import the required packages.

Declare the main class.

Give the “main ()” method.

Declare the string array that contains the names of the city.

Declare an integer array that contains the weight.

Create an object for unweighted graph.

Print the size of the graph, vertex of the graph, index of the vertex “Miami”, and the edges of the graph.

Call the function “maxInducedSubgraph ()”.

Print the size of the graph, vertex of the graph, index of the vertex “Miami”, and the edges of the graph.

Give function definition for “maxInducedSubgraph ()”.

Declare required variables

Do until the condition “(!Isdone && g.getSize() > 0)” fails.

Assign “true” to the variable.

Loop from 0 through size.

Check the condition “(g.getDegree(i) < k)”.

Call the function “remove_Vertex ()”.

Assign false to the variable.

Break the loop.

Return the graph.

Function definition for “UnweightedGraphInducedSubgraph ()”.

Construct the empty graph.

Construct a graph from vertices and edges stored in arrays.

Get the vertices and edges.

Construct a graph from vertices and edges stored in List.

Get the vertices and edges.

Construct a graph for integer vertices 0, 1, 2 and edge list.

Get the vertices and edges.

Construct a graph from integer vertices 0, 1, and edge array.

Get the vertices and edges.

Give function definition for “remove_Vertex ()”.

Check the condition “(vertices.contains(v))”.

Get the index.

Call the functions “vertices.remove ()”, and “neighbors.remove ()”.

Loop to remove the edges.

Loop from 0 through size.

Check the condition “(list.get(i).v == index)”. If it is true then remove the edge.

Else, increment the variable

Loop to reassign the labels.

Loop from 0 through size.

Check the condition “(list.get(i).u >= index)”. If the condition is true then get the edge

Check the condtion “(list.get(i).v >= index)”. If the condition is true then get the edge

Return “true”.

Else,

Return “false”.

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Students have asked these similar questions

When the FCC added Color Television to the Industry Standards, they went with the system developed in the 1940s by Peter Goldman for CBS. Question 15 options: True False Part of the reason that many critics disliked 1950s gameshows was the fact that gameshows offered one of the few opportunities to see unscripted interactions with "real" (average/non-famous) people on television. Question 16 options: True False The Andy Griffith Show is an example of the "rural revival" shows that become enormously popular on 1960s American television. Question 19 options: True False During the Network Era, the hours before primetime each day were exclusively devoted to locally-produced programming, not programming dictated by an affiliate station's parent network. Question 20 options: True False

Although color television was not added to the industry standard until 1956, CBS had been broadcasting selected special events in color as early as 1950. Question 1 options: True False Two key factors in creating the Network Era of American television were the FCC licensing freeze and ______________. Question 4 options: The Quiz Show Scandals Habitual Viewing Operation Frontal Lobes Drop-In Viewing Least Objectionable Programming was designed to embrace the public service-oriented vision of using television to elevate mass culture and enrich viewers. Question 6 options: True False By the end of the 1950s, all three remaining networks (NBC, CBS, & ABC) were broadcasting their entire nightly programming schedule in full color. Question 9 options: True False

7. See the code below and solve the following. public class Test { public static void main(String[] args) { int result = 0; } result = fn(2,3); System.out.println("The result is: + result); // fn(x, 1) = x // fn(x, y) = fn(x, y-1) + 2, when y>1 public static int fn(int x, int y) { if (x <= 1) return x; else return fn(x, y-1) + 2; } } 7-1. This program has a bug that leads to infinite recursion. Modify fn(int x, int y) method to fix the problem. (2 point) 7-2. Manually trace the recursive call, fn(2,3) and show the output (step by step). (2 point) 7-3. Can you identify the Base Case in recursive method fn(int x, int y)? (1 point)