Graph

G =(V,E) is a set V of vertices(nodes) and a collection E of pairs from V, called edges(arcs)

Undirected Edges

- represents a symmetric relation between two vertices
- degree of vertex is number of incident edges
- parallel edges: not that one edge between two vertices
- self-loop: edge connects vertex to itself

Walk (undirected paths)

Is sequence of vertices v1,v2, … , Vn such that there exists edges {v1,v2}, {v2,v3}, … {Vn-1, Vn}

Length (undirected paths)

Number of edges of a walk

If v1 =Vn closed otherwise open

Trail (undirected paths)

No edge is repeated

Circuit (undirected paths)

Is a closed trail

Path (undirected paths)

No vertex is repeated

Cycle (undirected paths)

A path with the same start and end vertices

Connected graph

If every pair of vertices is connected by a path

Simple graph

Is a graph with no self-loops and no parallel or multi-edges

Complete graph

Simple graph where an edge connects every pair of vertices

Subgraph

Sub graph of G if

- new V is a subset of V
- new E consists of edges {v,w} in E such that both v and w are in new V

Spanning sub graph

Consists of all of the vertices of G

-2^m spanning subgraphs

Tree (undirected)

And undirected graph such that:

- T is connected
- T has no cycle

Forest

Is an u directed graph without cycles

-connected components of forests are trees

Spanning tree

- of a connected graph is a spanning sub graph that is a tree
- is not unique unless the graph is a tree

Spanning forest

Is a spanning sub graph that is a forest

Directed Edges (arcs)

Represents an asymmetric relation between two vertices

- arc goes from source to destination
- indegree: number of incoming arcs
- outdegree: number of outgoing arcs

Simple diagraph

Is a graph with no self-loops and no parallel or multi-edges

-has O(n^2) edges

Connected digraph

Given vertices u and v we say v is reachable from u if there is a directed path from u to v

- connected if every pair of vertices is connected by an undirected path
- strongly connected if for every pair of vertices u and v, u is reachable from v and vis versa

Directed Acyclic graph (DAGs)

Is a directed graph with no cycles

-more general then trees, but less general that arbitrary directed graphs

Graph ADTs

- Edge list structure
- adjacency list structure
- adjacency-matrix structure