9/24/12

Graphs

Directed Graph G is described as pair (V,E) where V is finite set of nodes and E is binary relation in V.

E:(v1,v2) -> t; where v1, v2 are nodes in V, and t is arrow, in one direction, other direction or two directions, or no arrow at all.

This is read: relation E is function that associates value t from set of arrows to each of tuples: (v1,v2). Set of arrows consists of elements: arrow in one direction, arrow in other direction, arrow in two directions, no arrow at all.

E is called edge set. Graphically, nodes are pictured as circles, and edges are pictured as arrows. It is possible for loop to exist, connecting node to itself.

In oriented graph there are no arrows in two directions at once.

In Undirected Graph G = (V,E), edge set E is set of unordered pairs of nodes. There are no loops in undirected graphs.

If (u,v) is edge of directed graph G = (V,E), then edge (u,v) joins initial node (or tail) u, with destination node v. If (u,v) is edge of undirected graph G = (V,E), then edge (u,v) is incidental with u and v.

If (u,v) is edge of Graph G = (V,E), then we say, that node v is adjacent to node u. In undirected graph, adjacency relation is symmetrical (if u is adjacent to v, then v is adjacent to u).

Path in a graph is serie of nodes such as that for each of node pairs, there's an edge leading from first node to second - directed or not. First and last node in a path are called beginning and end of the path. About the edge that joins two nodes next to each other, we say that it belongs to a path.

Distance in a graph is the length of shortest path between two graph nodes.

Path is simple if there are no repeated nodes on it.

Cycle consists of a sequence of edges (arrows) starting and ending at the same edge, with each two consecutive edges in the sequence adjacent or incidental to each other in the graph. In a directed cycle, edges must have arrows pointing from previous edge to next, start and end up in first edge.

Graph is consistent if any two nodes can be connected by a path.

Graph Gs = (Vs, Es) is called subgraph, when there's a graph G = (V,E) and Vs is subset of V, and Es is subset of E.

We also take note of largest consistent subgraphs - any subgraph with maximum amount of nodes and edges that can belong to it is called such.


Source: [4], Wikipedia, [19].

No comments:

Post a Comment