**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 G

_{s}= (V

_{s}, E

_{s}) is called subgraph, when there's a graph G = (V,E) and V

_{s}is subset of V, and E

_{s}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