Unit 2 - Graph Theory

What is a connected graph?

• A graph with loops

• A graph where all vertices are isolated

• graph in which there is a path between every pair of vertices

• A graph with no edges

What is a disconnected graph?

• A graph with no vertices

• A graph with a cycle

• A graph in which some vertices are not connected by a path

• A graph with only one vertex

A component in a graph is:

• A cycle

• A disconnected edge

• A maximally connected subgraph

• A single edge

An Euler graph is a graph that:

• Has a cycle visiting each vertex once

• Has all vertices of even degree

• Has a loop

• Is disconnected

What is an Eulerian trail?

• A walk that uses every edge exactly once

• A walk that uses every vertex exactly once

• A trail with repeated vertices

• A trail with loops

Which operation on graphs combines two graphs into one without adding any new edges?

• Union

• Join

• Product

• Intersection

A Hamiltonian path:

• Visits every edge exactly once

• Visits every vertex exactly once

• Visits every vertex multiple times

• Repeats edges

Which of the following graphs always has a Hamiltonian circuit?

• Null graph

• Complete graph

• Bipartite graph

• Disconnected graph

The Travelling Salesman Problem (TSP) is based on:

• Eulerian path

• Minimum spanning tree

• Hamiltonian circuit

• Shortest path algorithm

In the Travelling Salesman Problem, the goal is to:

• Maximize the cost of the path

• Minimize the total distance while visiting all vertices once and returning to the start

• Visit each vertex more than once

• Find a tree