Data Structure GRAPH Definitions And Terminology | letsbug

1.  What is a Graph?

    - A graph G is a set of two tuples G = ( V, E ), where V is finite non-empty set of vertices and E is the set of pairs of vertices called edges. 

2. Adjacent Vertex

    - When there is an edge from one vertex to another then these vertices are called adjacent vertices.

3. Cycle

    - A path from a vertex to itself is called a cycle. Thus, a cycle is a path in which the initial and final vertices are same.

4.  Complete Graph

    - A graph G is said to be complete if every vertex in a graph is adjacent to every other vertex. In this graph, number of edges = n ( n - 1 ) / 2, where n = Number of vertices.

5.  Connected Graph

    - An undirected graph F is said to be connected if for every pair of distinct vertices Vi, Vj in V(G) there is a path from Vi to Vj. 

6.  Degree of a Vertex

    - It is the number of edges incident to a vertex. It is written as deg(U), where U is a vertex.

7.  In-degree of a Vertex

    - In directed graph, in-degree of a vertex 'v' is the number of edges for which 'v' is the head.

8.  Out-degree of a Vertex

    - In directed graph, the out-degree of a vertex 'v' is the total number of edges for which 'v' is the tail.

9.  Isolated Vertex

    - If any vertex does not belong to any edges then it is called isolated vertex..

10.  Source Vertex

    - A vertex with in-degree zero is called is called a source vertex, i.e. vertex has only outgoing edges and no incoming edges.

11.  Sink Vertex 

    - A vertex with out-degree zero is called a sink vertex i.e. vertex has only incoming

edge.  

12.  Acyclic Graph 

    - A graph without cycle is called acyclic graph.

13.  Subgraph

    - A subgraph of G is a graph G' such that V ( G' ) ⊆ V(G) and E(G') ⊆ E(G).

14.  Weighted Graph

    - A weighted graph is a graph in which every edge is assigned a weight. Weight in a graph denote the distance between the two vertices connected by the corresponding edge. The weight of an edge is also called its cost.

15.  Pendant Vertex

    - when in-degree of vertex is one and out-degree is zero then such a vertex is called pendant vertex.

16.  Spanning Tree

    - A spanning tree of a graph G = ( V, E) is a subgraph of G having all vertices of G and containing only those edges that are necessary to join all the vertices in the graph. A spanning tree does not not contain cycle in it.

17.  Path

    - A path is a sequence of distinct vertices, each adjacent to the next. The length of such a path is number of edges on the path.