|
A graph is a set of vertices and edges which connect them. A graph G consists of two things.
- A set I of elements called node or points or vertices.
- A set E of edges, such that each edge e in E is identified with a unique (unordered) pair[u,v] of nodes in V, denoted by e=[u,v].
Directed Graph:
A directed graph G, also called digraph, is the same as a multigraph except that each edge e in G is assigned a direction, or in other words each edge e is identified with an ordered pair (u,v) of nodes in G rather than an unorder pair [u,v].
Suppose G is a directed graph with a directed edge e=(u,v) then e is also called an arc.
Representation of Graph:
A graph must have at least one arc. We call arc a directed link between two nodes. For instance the arc (e,u) goes from tail node e to head node u. We call edge the corresponding undirected link. A minimal way to represent a graph is to give the number of nodes, the list of the tail nodes and the list of the head nodes. Each node has a number and each arc has a number. The numbers of nodes are consecutive and the number of arcs is consecutive.
Strongly Connected Graph:
A directed graph G is said to be connected or strongly connected if for each pair (u,v) of nodes in G there is a path from u to v and there is also a path from v to u. on the other hand, G is said to be unilaterally connected graph if for any pair (u,v) of nodes in G, there is a path from u to v or a path v to u.
Spanning Tree:
A spanning tree of a graph, G, is a set of |V|-1 edges that connect all vertices of the graph.
Minimum Spanning Tree:
The minimum spanning tree (MST) of a graph defines the cheapest subset of edges that keeps the graph in one connected component.
|
