Graphic Theory(1

Graphic Theory


G = (V, E), of two sets representing the nodes or vertices of the graph and the edges of the graph. An edge specifies which nodes have a connection between them. A graph can either be undirected or directed. An undirected graph, typically just called a graph, has edges that can be traversed in either direction.
A directed graph, also called a digraph, has edges that can only be traversed in one direction. For a digraph, our set of edges will have ordered pairs in which the first item is where the edge starts and the second is where the edge ends
Example:
Terminology :
A complete graph is a graph with an edge between every pair of nodes. If there are N nodes, there will be (N2 - N) / 2 edges in a complete graph without loop edges.
A subgraph (Vs, Es) of a graph or digraph (V, E) is one that has a subset of the vertices (Vs ?V) and edges (Es ? E) of the full graph.
A path between two nodes of a graph or digraph is a sequence of edges that can be traveled consecutively.
A path is said to have a length that represents the number of edges that make up the path. The path AB, BC, CD, DE has length 4.
A weighted graph or digraph is one where each edge has a value, called the weight, associated with it. In graph drawings, the weight will be written near the edge.
A path through a weighted graph has a cost that is the sum of the weights of each edge in the path. In a weighted graph, the shortest path between two nodes is the path with the smallest cost, even if it doesn’t have the fewest edge

Exercises1:
1. Draw the following graph: G = ({1, 2, 3, 4, 5, 6}, {{1, 2}, {1, 4},
{2, 5},{2, 6}, {3, 4}, {3, 5}, {3, 6}, {4, 5}, {4, 6}, {5, 6}}).
2. Draw the following digraph: G = ({1, 2, 3, 4, 5}, {(1, 2), (1, 4), (1, 5),
(2, 3), (2, 4), (2, 5), (3, 2), (3, 4), (3, 5), (4, 1), (4, 2), (4, 5), (5, 2),
(5, 3),(5, 4)}).
3. Give the set description for the
following graph:





4- Give the set description for the
following digraph





5. List all of the paths between node 1 and node 5 in the graph in Q3.
6. List all of the paths between node 1 and node 4 in the digraph in Q 4.
7. List all of the cycles that start at node 3 in the graph in Q 3.
8. List all of the cycles that start at node 7 in the digraph in Q 4.

Data Structure Methods for Graph:
There are two ways that we can store the graph or digraph information: an adjacency matrix or an adjacency list
An adjacency matrix gives us the ability to quickly access edge information, but if the graph is far from being a complete graph, there will be many more empty elements in the array than there are full elements.
An adjacency list uses space that is proportional to the number of edges in the graph, but the time to access edge information may be greater.

The Adjacency Matrix:
An adjacency matrix, AdjMat, for a graph G = (V, E), with |V| = N, will be stored as a two dimensional array of size N ×N.

for all i and j in the range 1 to N

The adjacency matrices for the graph and digraph figure in graphic section are
For weighted graphs and digraphs, the adjacency matrix entries would be ? if there is no edge and the weight for the edge in all other cases. The diagonal elements would be 0, because there is no cost to travel from a node to itself.
The Adjacency List:
An adjacency list, AdjList, for a graph G = (V, E), with |V| = N, will bestored as a one-dimensional array of size N, with each location being a pointer to a linked list.
For weighted graphs and digraphs, the adjacency list entries would have an additional field to hold the weight for that edge. The adjacency matrices for the graph and digraph figure in graphic section are:






Exercises2: consider questions of Exercises1 and answer the following :
1. Give the adjacency matrix for the graph in Q1
2. Give the adjacency matrix for the digraph in Q2
3. Give the adjacency matrix for the graph in Q3.
4. Give the adjacency matrix for the digraph in Q4.
5. Give the adjacency list for the graph in Q1.
6. Give the adjacency list for the digraph in Q2.
7. Give the adjacency list for the graph in Q3 .
8. Give the adjacency list for the digraph in Q4 .