Question

Define a graph. Draw a directed and undirected graph with 8 vertices and explain all the terminologies associated with that graph Note: Terminologies are cycles, path, directed and undirected graph, circuit, loop, adjacency, degrees, Euler circuit, Hamiltonian circuit

Answer 1

Answer:

A graph is a collection of set of edges E and vertices V, where each edge joins pair of vertices.

A graph is undirected when the edges has no direction.

A graph is directed when the edges has confined direction.

An edge is directed if it is defined to come out from one vertex and goes to another fixed vertex.

A loop is an edge from a vertex to itself.

A path from a vertex x to another vertex y is a sequence of distinct edges that joins sequence of distinct vertices:

                   (x,$x_{1}$)→($x_{1}$, $x_{2}$)→($x_{2}$, $x_{i}$)→ .... → ($x_{j}$,y)

A cycle is path that starts and ends at same vertex.

A circuit is a path that starts and ends at same vertex, but not necessarily contain distinct vertices.

An Euler circuit is circuit that traverse each edge of the graph exactly once and covers all vertices.

An Hamiltonian circuit is a simple circuit that traverse each vertex of the graph exactly once and covers all edges.

Degree of a vertex is the number of edges incident on it.

• In case of undirected graph the number of edges incident on the vertex is it's degree.
• but in case of directed graph the number of edges coming out of the vertex is it's out-degree and the number of edges going to the vertex is it's in-degree.

Explanation: