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