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.