Answer to Question #140765 in Discrete Mathematics for Joseph Se

Question

A. Give a brief definition of the following:

1. Graph
2. Degree of a vertex
3. Isomorphic graphs

B. Give 4 types of graphs and give a brief description (you may describe in words or just draw a sample graph).

Answer 1

Description: A graph ‘G’ is a set of vertex, called nodes ‘v’ which are connected by edges, called links ‘e'. Thus G= (v , e).

Degree of vertex is the number of edges of outgoing of that vertex

Isomorphic graph

• Their number of components (vertices and edges) are same.
• Their edge connectivity is retained.

Types of graph

• Null graph: Also called an empty graph, a null graph is a graph in which there are no edges between any of its vertices.
• Connected graph: A graph in which there is a path of edges between every pair of vertices in the graph. Mary's graph is a connected graph, since there is a way to get from every city on the map to every other city.
• Disconnected graph: A graph in which the path of edges does not always connect every vertex.
• Bipartite graph: A graph that can be split into two sets of vertices such that edges only go between sets, not within them.
• Weighted graph: A graph in which weights, or numerical values, are assigned to each of the edges. Mary's graph is a weighted graph, where the distances between the cities are the weights of the edges.
• Directed graph: A graph in which the edges are directed by arrows, indicating that the relationship, represented by the edge, only applies from one vertex to the other, but not the other way around. In other words, if a directed edge has an arrow from A to B, A is related to B, but B is not related to A.
• Undirected graph: A graph whose edges are not directed. Mary's graph is an undirected graph, because the routes between cities go both ways.
• Simple graph: An undirected graph in which there is at most one edge between each pair of vertices, and there are no loops, which is an edge from a vertex to itself.
• Multi-graph: A graph in which there are multiple edges between any pair of vertices or there are edges from a vertex to itself