To get the best deal on Tutoring, call 1-855-666-7440 (Toll Free)
Top

Graph Theory

A graph consists of the collection of vertices and edges, where an edge is a connection between any two vertices.
We can make a graph by drawing some lines connecting edges, which are joined by vertices.

Graph Theory Basics:
1.    A directed graph which is generally denoted as G = (V, E) have a finite set V and a binary relation on V.
2.    An undirected graph denoted as G = (V, E) has a finite set V and a set of multi-sets of two elements from V.
3.    A graph is said to be complete if every pair of its distinct vertices is adjacent.
4.    The precise way to represent a graph is to say that it is made up of the sets of vertices and the set of edges between these vertices.
5.    A sub graph H of a graph G = (V, E) is a sub-graph if H = (V', E') satisfies V' is contained in V and E' is contained in E.
6.    A simple path is a path with no vertex repeated.
7.    If there exists a path from every vertex to every other vertex in the graph, then the graph is known as connected. A connected graph would remain the same, if taken by any vertex, if the vertices are physical and the edges as strings connecting them.
8.    A cycle is a path, (a way from a vertex back to itself), which is a simple path, but here, the first and the last vertex are the same, that is the first vertex meets the last after completing its cycle.
9.    A graph with no cycles is called a tree, and in a tree, there is only a single path between any two nodes. A tree on N vertices has exactly N - 1 edges.
10.    A sub graph that has all the vertices and forms a tree is known as a spanning tree of a graph.
11.    A group of disconnected trees is called a forest.
12.    The graphs which have a direction associated with each edge are known as directed graphs.
13.    An edge ab in a directed graph can be used in a path which goes from a to b only not from b to a.

Related Calculators
Calculator for Graphing circle graph calculator
Ellipse Graphing Calculator Equation Graphing Calculator
 

Graph Theory Example

Back to Top

Solved Example

Question: Consider the graph as {A1, B, C, D, E, F, G, H, I, J, K, L, M} as the set of vertices, and the set {A1G, A1B, A1C, LM, JM, JL, JK, ED, FD, HI, FE, A1F, GE} as the set of edges, which are connecting the above set of vertices. Find
1.    a path,
2.    a path which is not simple,
3.    the number of connected components
4.    and a cyclic path.
Solution:
 
From the above graph, we can conclude that:
1.    BA1FEG is a path from B to G.
2.    BA1FEGA1C is not a simple path
3.    It has three connected components as {I, H}, {J, K, L, M} and {A1, B, C, D, E, F, G}
4.    The path A1FEGA1 is a cycle.
 


More topics in  Graph Theory
Graph Coloring Chromatic Number
Edge Coloring Trees
*AP and SAT are registered trademarks of the College Board.