General Flashcards
What is a Graph?
A finite, nonempty set V, the vertex set along with set E, the edge set, whose elements e in E are pairs (a,b) with a,b in V
What is an Undirected Graph?
An undirected graph is a graph which the edge set consists of unordered pairs
What is a Directed Graph?
A Digraph/Directed graph is a graph in which pairs are ordered
A bipartile graph?
A graph is bipartile if it is a non empty edge set, and it’s vertex set can be decomposed into two disjoint nonempty subsets
Define the degree of a vertex in an undirected graph
The degree of a vertex is the no of edges that include the vertex
Define a neighbour of vertex v
In a graph a vertex u is a neighbour of a vertex v if (u,v)eE
Define a successor of a vertex V
In a directed graph a successor of a vertex v is a vertex u such that (v,u)eE
Define a predecessor for vertex v
In a directed graph a predecessor of a vertex v is a vertex u such that (u,v)eE
What does it mean for two graphs to be isomorphic?
Two graphs are said to be isomorphic if there exists a bijection a(v)-> v_2 such that (u,v)eE if and only if (a(u),a(v))eE
What is a Chromatic number?
The smallest K which G has been a K colouring
Define the floor and ceiling of X
Floor is the largest integer that is equal or smaller than X
The ceiling is the largest integer that is equal or larger than X
Define a walk and it’s length?
A set of edges is a walk if there exists a corresponding sequence of vertices
Its length is the number of edges in the sequence
Define a trail
A trail is a walk where all the edges are distinct
Define a path
A path is a trail in which all the vertices are distinct
Define a cycle
A cycle is a path that includes 3 or more edges
Define what it means for two verticies to be connected
In a graph two vertices are said to be connected if there is a walk between them
Define what it means for a graph to be connected
A graph is connected in which every pair of vertices is connected
Define what it means for a to be strongly connected to b
A and b in a digraph are strongly connected if there is a walk from a to b AND a walk from b to a
Define what it means for a to be accessible from b
In a discredited graph a vertex b is accessible from a vertex a if there is a walk a to b
Define what it means for a graph to be strongly connected
A directed graph is said to be strongly connected if all pairs of vertices are strongly connected
Define what it means for a graph to be weakly connected
A directed graph is weakly connected when one vertex ignore the directedness of the edges it becomes a connected undirected graph
Define what it means for vertex b to be accessible from vertex a
In a Digraph a vertex b is accessible from a if there is a walk from a to b
Define what it means for graph to be acyclic?
A graph is acyclic if it has no cycles
What is a Tree?
A tree is a connected acyclic graph
What is a Forest?
A forest is a graph who’s connected components are trees
What is a leaf?
A vertex is a leaf in a tree if it has degree 1
What does it mean for a vertex to be isolated
if the vertex has a degree zero
what is a Spanning Tree
A subgraph of a graph is a spanning tree if it is a tree containing every vertex in v
What is a root?
A vertex in a digraph is a root of every other vertex if it is accessible to all
What is an arborescence/ Directed Tree?
A digraph is a DT/arborescence if it contains a root and if you ignore the directness it becomes a connected tree
What is a Spanning arborescence?
A subgraph of a Digraph is a SA if its an arborescence that contains all vertices in G
What is a permutation?
A permutation of n objects is a bijection from set {1,…,n}
Define the fix(sigma)
fix(sigma)={j | sigma(j)=j}
Define the sign(sigma)?
identity sigma =+1
If sigma is of a singular cycle length L then sign is (-1)^L-1
if sigma can be decomposed into k disjoint cycles then the sign ,L=sum(all cycles) (-1)^L-k
What is a Spreg?
A single predecessor graph is a directed graph in which each vertex other than the distinguished vertex V has exactly on predecessor while V has none
What is an Eulerian Trail?
It is a trail which includes all edges once only
What is an Eulerian tour/cycle?
It is a closed eulerian trail
What does it mean for a Graph to be eulerian?
A multigraph is eulerian if it contains a eulerian tour
What is an Hamiltonian Trail?
A hamiltonian trail is a trail which includes every vertex in V (once?)
What is an Hamiltonian tour/cycle?
Is a closed hamiltonian trail
What does it mean for a graph to be Hamiltonian
A graph is Hamiltonian if it contains a hamiltonian tour
What is an bridge
An edge is a bridge iff it G\e has more than one connected component
What is a Planar Diagram ?
A planar diagram for a graph G with Edge set E is a collection of simple curves that represent edges and have property g_i and g_j iff edges e_i and e_j iff the edges meet at their corresponding vertex
Girth?
If a graph contains at least one cycle then the girth is the length of the shortest cycle
What is a subdivision of a graph?
A subdisvion of a graph is a graph from by removing an edge and replacing it with a path, with each new vertex having a degree of 2
What does it mean for two graphs to be homeomorphic?
two graphs are said to be homoeopmorphic if they are isomorphic subdivisions of the same graph.
