Monday, 3 August 2015

Graph Theory: Terms to remember

From AGT(1.1-1.2) and MGT(I.1)
Definitions encountered in graph theory:

~ Basic graph-related definitions
(undirected) graph
directed graph
simple graph
vertex (set)
edge (set)
arc (set)
path
cycle
walk
trail
circuit
(dis)connected
order, |G|
size, e(G)
degree sequence
distance
cutvertex
bridge
loop

~ Relations between components of graphs
adjacency
incidence
neighbour
(open / closed) neighbourhood
(out / in) degree

~ Relations between graphs
equality / isomorphism
subgraph
complement

~ Subgraph-related definitions
spanning subgraph
induced subgraph
clique
independent vertex set
independent path set
connected component
(oriented graph) - not strictly a subgraph

~ Types of graph
complete
k-regular
empty
null
cyclic
acyclic
tree
spanning tree
forest
bipartite / r-partite
(hypergraph) - not strictly a graph
(multigraph) - not strictly a graph

No comments:

Post a Comment