Basic Concepts Of Graph Theory
Today i will be discussing on Graph Theory in discrete mathematics,normally, when we hear the word graph we think of the x-y plane,but when it comes to discrete mathematics a graph is simply a set of vertices and edges where the edges are drawn to connect two or more vertices together.
This graphs have a wide range of applications in mathematics ranging from mathematical modelling to mathematical biology.
Graph models are used in modelling organic carbon compounds to see relationships between the hydrocarbons,electrcal model and modelling the geographical locations in order to determine shortest path of travel.
firstly,
i will like to begin by giving the definition of some basic terms in graph theory.
(1) Graph: A graph G consists of vertices which is a non-empty set of objects,and edges which is not necessarily non-empty, in order words, a graph is an ordered pair G=(V,E) where V is a finite set of elements and E is a set of 2-subsets of V.
for a clear picture we can illustrate a graph as:
here $V=\{v_1,v_2,v_3\}$ and $E=\{\{v_1,v_2\},\{v_2,v_3\},\{v_1,v_3\}\}$.
(2) Vertices: the vertices also known as vertex in singular, are drawn as thickened points such as the one shown above.
(3) Edge: An edge connects two vertices or connects a vertex to itself.these edges are drawn as line segments or arcs.
(4) Loop: This is an edge that goes from a vertex back to the same vertex e.g below is an example of a loop.
(5) Multiple Edge: This is an edge that goes between a vertex where there has already been an edge.So its just like saying its a vertex with more than an edge connected to it.
(6) Simple Graphs: simple graphs are simply graphs that has no loops and multiple edges.example is the triangular graph,star graph and so many other types of graphs,all the graphs shown here are simple graphs except the "loop".
(7) Directed Graphs: This is a graph where the sets in the edges are ordered OR in other words we can define a directed graph as a graph where each edge has a direction associated to it. e.g is the graph below
$E=(v_1,v_3),(v_2,v_3)$
(8) Order of Graph: this is denoted by $|V|$,it is the number or size of the vertices.
(9) Size of Graph: This is denoted by $|E|$, it is the number of edges a graph has.
Example of Graphs
Below is a graph, and we are going to determine the order of the graph and the size of graph by constructing the graph using the given set of data below.
Let $V=\{v_1,v_2,v_3,v_4,v_5\}$ and $\{v_1v_2,v_2v_3,v_3v_4,v_4v_1,v_1v_5\}$.
Now note that in drawing a graph, there is no special arrangement or drawing that must be followed, the must important
thing is to represent the given set of information correctly.
here $|V|=5$ and $|E|=5$.we can see the constructed graph is a simple graph because it has no loops and multiple edges.
(10) A Path: A path $P_n$ is a graph whose vertices can be arranged in a sequence such as $v_1,v_2,v_3,...,V_n$ such that the edge set is $E=\{vivi+1:i=1,...,n-1\}$,Now note that in every path, the edge is always lesser than the vertex by one i.e if we have a path of size 4 i.e $p_4$, then the graph is denoted by
here the vertex is 4 and the edge is 3.
(11) A Cycle: This is a graph $C_n$ whose vertices can be arranged in a cyclic sequence $(v_1,v_2,v_3,...,v_n)$ such that the edge set is $E=\{v_iv_{i+1}:i=1,...,n-1\}\bigcup\{v_1v_n\}$.
Note that the edge and vertices of a cycle always have equal size, e.g the cyclic graph below has 6 vertices and 6 edges
(12) triangle graph:this is simply a cycle with 3 vertices or a complete graph(i will be treating complete graphs in my upcoming topics) with 3 vertices. a triangular graph is written as
$\text{triangle}=c_3=k_3$,below is an illustration of a triangle graph.
(13) Ends of Edges: if there exists an edge say $e=uv$,then u and v are ends of the edges e.
(14) Adjacent Graph: If u and v are connected by the edge e, then u and v are adjacent or neighbours.
(15) If two edges have a common end then they are adjacent e.g
edges of $v_2$ and $v_3$ have a common end at $v_1$, hence they are adjacent.
In my next discussion i will be looking at the families and forms of graphs. thank you
Today i will be discussing on Graph Theory in discrete mathematics,normally, when we hear the word graph we think of the x-y plane,but when it comes to discrete mathematics a graph is simply a set of vertices and edges where the edges are drawn to connect two or more vertices together.
This graphs have a wide range of applications in mathematics ranging from mathematical modelling to mathematical biology.
Graph models are used in modelling organic carbon compounds to see relationships between the hydrocarbons,electrcal model and modelling the geographical locations in order to determine shortest path of travel.
firstly,
i will like to begin by giving the definition of some basic terms in graph theory.
(1) Graph: A graph G consists of vertices which is a non-empty set of objects,and edges which is not necessarily non-empty, in order words, a graph is an ordered pair G=(V,E) where V is a finite set of elements and E is a set of 2-subsets of V.
for a clear picture we can illustrate a graph as:
here $V=\{v_1,v_2,v_3\}$ and $E=\{\{v_1,v_2\},\{v_2,v_3\},\{v_1,v_3\}\}$.
(2) Vertices: the vertices also known as vertex in singular, are drawn as thickened points such as the one shown above.
(3) Edge: An edge connects two vertices or connects a vertex to itself.these edges are drawn as line segments or arcs.
(4) Loop: This is an edge that goes from a vertex back to the same vertex e.g below is an example of a loop.
(5) Multiple Edge: This is an edge that goes between a vertex where there has already been an edge.So its just like saying its a vertex with more than an edge connected to it.
(6) Simple Graphs: simple graphs are simply graphs that has no loops and multiple edges.example is the triangular graph,star graph and so many other types of graphs,all the graphs shown here are simple graphs except the "loop".
(7) Directed Graphs: This is a graph where the sets in the edges are ordered OR in other words we can define a directed graph as a graph where each edge has a direction associated to it. e.g is the graph below
$E=(v_1,v_3),(v_2,v_3)$
(8) Order of Graph: this is denoted by $|V|$,it is the number or size of the vertices.
(9) Size of Graph: This is denoted by $|E|$, it is the number of edges a graph has.
Example of Graphs
Below is a graph, and we are going to determine the order of the graph and the size of graph by constructing the graph using the given set of data below.
Let $V=\{v_1,v_2,v_3,v_4,v_5\}$ and $\{v_1v_2,v_2v_3,v_3v_4,v_4v_1,v_1v_5\}$.
Now note that in drawing a graph, there is no special arrangement or drawing that must be followed, the must important
thing is to represent the given set of information correctly.
here $|V|=5$ and $|E|=5$.we can see the constructed graph is a simple graph because it has no loops and multiple edges.
(10) A Path: A path $P_n$ is a graph whose vertices can be arranged in a sequence such as $v_1,v_2,v_3,...,V_n$ such that the edge set is $E=\{vivi+1:i=1,...,n-1\}$,Now note that in every path, the edge is always lesser than the vertex by one i.e if we have a path of size 4 i.e $p_4$, then the graph is denoted by
here the vertex is 4 and the edge is 3.
(11) A Cycle: This is a graph $C_n$ whose vertices can be arranged in a cyclic sequence $(v_1,v_2,v_3,...,v_n)$ such that the edge set is $E=\{v_iv_{i+1}:i=1,...,n-1\}\bigcup\{v_1v_n\}$.
Note that the edge and vertices of a cycle always have equal size, e.g the cyclic graph below has 6 vertices and 6 edges
(12) triangle graph:this is simply a cycle with 3 vertices or a complete graph(i will be treating complete graphs in my upcoming topics) with 3 vertices. a triangular graph is written as
$\text{triangle}=c_3=k_3$,below is an illustration of a triangle graph.
(13) Ends of Edges: if there exists an edge say $e=uv$,then u and v are ends of the edges e.
(14) Adjacent Graph: If u and v are connected by the edge e, then u and v are adjacent or neighbours.
(15) If two edges have a common end then they are adjacent e.g
edges of $v_2$ and $v_3$ have a common end at $v_1$, hence they are adjacent.
In my next discussion i will be looking at the families and forms of graphs. thank you
Posts
0 Comments
Comments