Basic Terminologies in Graph

Basic Terminologies

Complete graph: If an undirected graph of n vertices consists of n(n-1)/2 number of edges then it is called as complete graph.

The graph shown in the Fig. 5.4.1 is a complete graph.

Subgraph: A subgraph G' of graph G is a graph such that the set of vertices. and set of edges of G' are proper subset of the set of edges of G.

Connected graph: An undirected graph is said to be connected if for every pair of distinct vertices V; and V; in V(G) there is a graph from V; to V; in G.

Weighted graph: A weighted graph is a graph which consists of weights along wih its edges.

Path: A path is denoted using sequence of vertices and there exists an edge from one vertex to next vertex.

Cycle : A closed walk through the graph with repeated vertices, mostly having the same starting and endig vertex is called a cycle.

Component: The maximal connected subgraph of a graph is called component of a graph.

For example: Following are 3 components of a graph.

Indegree and Outdegree

The degree of vertex is the number of edges associated with the vertex.

Indegree of a vertex is the number of edges that incident to that vertex. Outdegree of the vertex is total number of edges that are going away from the vertex.

Self Loop

Self loop is an edge that connects the same vertex to itself.