Discussion over Week 7 Problems_SU21

pdf

School

University of Illinois, Urbana Champaign *

*We aren’t endorsed by this school

Course

225

Subject

Computer Science

Date

Dec 6, 2023

Type

pdf

Pages

Uploaded by ProfPrairieDogMaster890

Note: This is an open-book and open-notes assignment. Please don’t take help from the internet. Instruction: You must not choose similar problems. Question Set 1: (a) Suppose that there are four employees in the computer support group of the School of Engineering of a large university. Each employee will be assigned to support one of four different areas: hardware, software, networking, and wireless. Suppose that Ping is qualified to support hardware, networking, and wireless; Quiggley is qualified to support software and networking; Ruiz is qualified to support networking and wireless, and Sitea is qualified to support hardware and software. Use a bipartite graph to model the four employees and their qualifications. (b) Draw a graph having the given properties or explain why no such graph exists: I. Simple graph; five vertices having degrees 2, 2, 4, 4, 4 II. Graph with four vertices having degrees 1, 2, 3, 4 Question Set 2: (a) For which values of m and n does the graph contain an Euler circuit? (b) Consider the following definitions: o A tournament graph is a directed graph with the property that no edge connects a vertex to itself, and between any two vertices there is at most one edge. o A complete (or round-robin) tournament graph is a tournament graph with the property that between any two distinct vertices there is exactly one edge. o A single-elimination tournament graph is a tournament graph with the properties that: (i) one vertex (the champion) has no edge terminating at it and at least one edge initiating from it; (ii) every other vertex is the terminal vertex of exactly one edge; and (iii) there is a path from the champion vertex to every other vertex. Now answer the following questions: I. How many edges does a complete tournament graph with n vertices have? II. How many edges does a single-elimination tournament graph with n vertices have?

Question Set 3: (a) Suppose that there are five young women and six young men on an island. Each woman is willing to marry some of the men on the island and each man is willing to marry any woman who is willing to marry him. Suppose that Anna is willing to marry Jason, Larry, and Matt; Barbara is willing to marry Kevin and Larry; Carol is willing to marry Jason, Nick, and Oscar; Diane is willing to marry Jason, Larry, Nick, and Oscar; and Elizabeth is willing to marry Jason and Matt. Model the possible marriages on the island using a bipartite graph. (b) Answer the following questions: I. When does the complete graph K n contain an Euler circuit? II. When does the complete bipartite graph K m,n contain an Euler circuit? Question Set 4: (a) Determine whether there is an Euler trail from b to c in the following graphs. If there is, find such a trail. If there is no such trail, explain why not. (b) Use the pigeonhole principle to show that a simple graph with n ≥ 2 vertices, has two vertices of the same degree.

Question Set 5: (a) Prove the statement – “ If a graph G contains a circuit from v to v, then G contains a simple circuit from v to v”. (b) Use Dijkstra’s algorithm to find the shortest path from a to z in the following graph: Direction: Please provide a table to show the action of Dijkstra's Algorithm to find the shortest path between two vertices. And you are required to provide the shortest path and its length in the end. Question Set 6: (a) Use Dijkstra’s algorithm to find a least expensive combination of flights connecting the pairs of cities: I. Boston and San Francisco II. Miami and Los Angeles, using the fares shown in the following figure:

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

Direction: Please provide a table (for each case) to show the action of Dijkstra's Algorithm to find the least expensive combination of flights between two vertices. And you are required to provide the least expensive combination of flights and its cost right after the table. (b) Find all the simple circuits in the following graph: Question Set 7: (a) Find all connected subgraphs of the following graph containing all of the vertices of the original graph and having as few edges as possible. Which are paths? Which are circuits? Which are simple circuits? (b) Suppose r and s are any positive integers. Does there exist a graph G with the property that G has vertices of degrees r and s and of no other degrees? Explain. Question Set 8: (a) Use the result of Example 4.9.9 (of the required textbook) to show that the number of edges of a simple graph with 𝑛𝑛 vertices is less than or equal to 𝑛𝑛 ( 𝑛𝑛−1 ) 2 .

(b) Use Dijkstra’s algorithm to find the shortest path from a to z in the following graph: Direction: Please provide a table to show the action of Dijkstra's Algorithm to find the shortest path between two vertices. And you are required to provide the shortest path and its length in the end. Question Set 9: (a) Determine which of the following graphs has an Euler circuit. Construct such a circuit when one exists. If no Euler circuit exists, determine whether the graph has an Euler trail and construct such a trail if one exists. (b) In a group of 25 people, is it possible for each to shake hands with exactly 3 other people? Justify your answer.

Question Set 10: (a) A simple graph is called regular if every vertex of this graph has the same degree. A regular graph is called n-regular if every vertex in this graph has degree n. Now answer the following questions - I. For which values of m and n is K m,n regular? II. How many vertices does a regular graph of degree four with 10 edges have? (b) Use Dijkstra’s algorithm for the airline route system of the following figure to find the shortest distance from Nashville to Minneapolis. Direction: Please provide a table to show the action of Dijkstra's Algorithm to find the shortest path between two vertices. And you are required to provide the shortest distance and its length in the end. Question Set 11: (a) Find which of the following graphs are bipartite. If yes, redraw the bipartite graphs so that their bipartite nature is evident. If not, prove why the graph is not bipartite by arguing by contradiction.

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

(b) A sports conference has 11 teams. It was proposed that each team play precisely one game against each of exactly nine other conference teams. Prove that this proposal is impossible to implement. Question Set 12: (a) Find a combination of flights with the least total air time between the pairs of cities: a) New York and Los Angeles b) Miami and Los Angeles, using the flight times shown in the following figure. Direction: Please provide a table to show the action of Dijkstra's Algorithm to find the least air time between two vertices. And you are required to provide the least air time and its duration in the end. (b) In a group of two or more people, must there always be at least two people who are acquainted with the same number of people within the group? Why? Question Set 13: (a) Determine whether the given graph has an Euler circuit. If it does, find such a circuit. If it does not, give an argument to show why no such circuit exists.

(b) Answer the following questions: I. In a group of 4 people, is it possible for each person to have exactly 3 friends? Justify your answer. II. A graph has vertices of degrees 1, 1, 4, 4, and 6. How many edges does the graph have? Question Set 14: (a) Determine whether the picture shown can be drawn with a pencil in a continuous motion without lifting the pencil or retracing part of the following picture? (b) Answer the following questions: I. Describe a graph model that represents a subway system in a large city. Should edges be directed or undirected? Should multiple edges be allowed? Should loops be allowed? II. For each course at a university, there may be one or more other courses that are its prerequisites. How can a graph be used to model these courses and which courses are prerequisites for which courses? Should edges be directed or undirected? Looking at the graph model, how can we find courses that do not have

any prerequisites and how can we find courses that are not the prerequisite for any other courses? Question Set 15: (a) Answer the following questions: I. How many subgraphs with at least one vertex does K 3 have? II. Can a simple graph exist with 15 vertices each of degree five? (b) The following is a floor plan of a house. Is it possible to enter the house in room A , travel through every interior doorway of the house exactly once, and exit out of room E ? If so, how can this be done? Question Set 16: (a) The complementary graph 𝐺𝐺 ̅ of a simple graph 𝐺𝐺 has the same vertices as 𝐺𝐺 . Two vertices are adjacent in 𝐺𝐺 ̅ if and only if they are not adjacent in 𝐺𝐺 . Now, find the complement of the graph K 3,2 , the complete bipartite graph on (3, 2) vertices. (b) An edge whose removal disconnects the graph of which it is a part is called a bridge . Find all bridges for each of the following graphs.

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

Question Set 1 7 : (a) For which values of n does the n-cube (https://en.wikipedia.org/wiki/Hypercube_graph contain) an Euler cycle? Justify your answer. (b) Answer the following questions: (i) Is it possible for a graph to have both an Euler path and Euler circuit? Explain your answer. (ii) The complementary graph G of a simple graph G has the same vertices as G. Two vertices are adjacent in G if and only if they are not adjacent in G. If G is a simple graph with 12 edges and G has 9 edges, how many vertices does G have? Question Set 1 8 : (a) Answer the following questions: (i) Explain how to find a path with the least number of edges between two vertices in an undirected graph by considering it as a shortest path problem in a weighted graph. (ii) Is a shortest path between vertices in a weighted graph unique if the weights of edges are distinct? Justify your answer. (b) Find a shortest path(in mileage) between each of the following pairs of cities in the airline system: (i) Boston and San Francisco (ii) Miami and Denver using the following figure: __ __

Related Documents

CS171-Lab1.pdf

CPSC Assignment 3.docx

Test_ Exam2 bcis 466 _ Quizlet.pdf

Week 2 Reading Quiz.pdf

Strat HW 04 Decision Analysis homework.pptx

OTCL 520 Exam 2.docx

HW 3.docx

infograph script first draft.docx

PBDMS HW3 (2).docx

CS3410_Assignment3.docx

PBDMS HW3 (1).docx

Lab 1 - Debugging New.docx

Recommended textbooks for you

C++ for Engineers and Scientists

Computer Science

ISBN:9781133187844

Author:Bronson, Gary J.

Publisher:Course Technology Ptr

Operations Research : Applications and Algorithms

Computer Science

ISBN:9780534380588

Author:Wayne L. Winston

Publisher:Brooks Cole

Programming Logic & Design Comprehensive

Computer Science

ISBN:9781337669405

Author:FARRELL

Publisher:Cengage

C++ Programming: From Problem Analysis to Program...

Computer Science

ISBN:9781337102087

Author:D. S. Malik

Publisher:Cengage Learning

Principles of Information Systems (MindTap Course...

Computer Science

ISBN:9781285867168

Author:Ralph Stair, George Reynolds

Publisher:Cengage Learning

Fundamentals of Information Systems

Computer Science

ISBN:9781305082168

Author:Ralph Stair, George Reynolds

Publisher:Cengage Learning

SEE MORE TEXTBOOKS

Recommended textbooks for you

C++ for Engineers and Scientists
Computer Science
ISBN:9781133187844
Author:Bronson, Gary J.
Publisher:Course Technology Ptr
Operations Research : Applications and Algorithms
Computer Science
ISBN:9780534380588
Author:Wayne L. Winston
Publisher:Brooks Cole
Programming Logic & Design Comprehensive
Computer Science
ISBN:9781337669405
Author:FARRELL
Publisher:Cengage
C++ Programming: From Problem Analysis to Program...
Computer Science
ISBN:9781337102087
Author:D. S. Malik
Publisher:Cengage Learning
Principles of Information Systems (MindTap Course...
Computer Science
ISBN:9781285867168
Author:Ralph Stair, George Reynolds
Publisher:Cengage Learning
Fundamentals of Information Systems
Computer Science
ISBN:9781305082168
Author:Ralph Stair, George Reynolds
Publisher:Cengage Learning