A Blog about Programming,Algorithms,Coding Competitions, and Discrete Mathematics!
Hello Friends, I'm gonna about Graph Theory in my upcoming posts, so here are some basic Graph terminology which will form a base to understand Graph Theory and Algorithms.
Overview
- Definitions: Vertices, edges, paths, etc
- Representations: Adjacency list and adjacency matrix
Definitions: Graph, Vertices, Edges
- Define a graph G = (V, E) by defining a pair of sets:
- V = a set of vertices
- E = a set of edges
- Edges:
- Each edge is defined by a pair of vertices
- An edge connects the vertices that define it
- In some cases, the vertices can be the same
- Vertices:
- Vertices also called nodes
- Denote vertices with labels
- Representation:
- Represent vertices with circles, perhaps containing a label
- Represent edges with lines between circles
- Example:
- V = {A,B,C,D}
- E = {(A,B),(A,C),(A,D),(B,D),(C,D)}
Motivation
- Many algorithms use a graph representation to represent data or the problem to be solved
- Examples:
- Cities with distances between
- Roads with distances between intersection points
- Course prerequisites
- Network
- Social networks
- Program call graph and variable dependency graph