Graph Theory Flashcards
graph
A graph, G=(V,E) is a finite set of vertices V and a finite set of Edges E where each edge (u,v) connects two vertices, u and v.
Adjacent
Two vertices, u and v of a graph are adjacent if there exists an edge (u,v).
Self loop
A self-loop is an edge (u,u).
multi-graph
A multi graph can have multiple edges between the same two vertices and self loops.
Incident
If (u,v) is an edge in a graph G, (u,v) is an incident to vertices u and v.
Degree
A degree of a vertex is the number of edges incident on it.
isolated
A vertex who’s degree is 0 is isolated.
Simple path
A path is simple if all vertices in the path are distinct.
Subpath
A subpath of a path is a continuous subsequence of its vertices.
Path
A path of length k from a vertex u to a vertex u’ is a sequence (v0,v1,v2,…,vk) of vertices such that u=v0, u’=vk and (vi-1,vi) is an edge in E for i=1,2,…,k. The length is the number of edges in the path.
Length k
The length is the number of edges in the path.
Cycle
A cycle s a path with k>0 where v0=vk, and all the edges are distinct.
Simple cycle
A cycle is simple if the vertices are distinct.
Acyclic
A graph with no simple cycles is acyclic
Connected
A graph is connected if every vertices is reachable from all other vertices
Connected components
The connected components are the equivalence classes of vertices under the “is reachable from” relation.
Hamiltonian cycle
A Hamiltonian cycle is a simple circuit that traverses all vertices. Named after sir Hamilton 1800s
Hamiltonian path
A Hamiltonian path is a simple path that traverses all vertices.
Complete graph of n vertices
A complete graph of vertices, Kn in which every pair of vertices is adjacent.
Bipartite graph of n vertices
A Bipartite Graph of n vertices is a graph in which the n vertices can be partitioned into two sets V1 and V2 such that for every edge (u, v), u is in one of
the sets and v is in the other. Km,n is the Complete
Bipartite graph where |V1|= m and |V2|= n.
Predicate
A predicate is a proposition who’s truth depends on the value of on or more variables of a propositional function. Notation: P(x), Q(x,y), R(a,b,c,d) etc
Universe of discourse
The universe of discourse specifies the possible values of the variable(s) in the predicate.
Quantifiers
Quantifiers such as E and A are symbols that are used to give more details about the predicate.
Universal Quantification
Universal Quantification A of P(x) is the proposition
“P(x) is true for all values of x in some set D”
