Module 1 Flashcards
Graph
Let V be a finite non empty set and E be the subset of VxV then G=(V,E) is called a Graph, where V is the set of vertices and E is the set of Edges
Trvial Graph
graph with a single vertex
Null(empty Graph)
No edges
Isolated Vertex
a Vertex that is not adjacent to any other vertex
Parallel edge
in a graph G=(v,e) if more than one edge is associated with a pair of vertices than these edges are called parallel edge
Order and Size
If G=(V,E) be a finite grapgh where V(G) denotes the number of vertices in G and is called Order of that graph and E(G) denotes number of Edges in G and is called the size of G
ie
order = number of vertices
size = number of edges
Simple Graph
Graph with no self loops or parallel edges
Incidence on graph
When a vertex vi is the end vertex of edge ei then ei and vi are said to be incident with each other
adjacent vertex
two vertices are said to be adjacent if they are the end vertices of the same edge
degree of a vertex
no of edges connected to it (self loop is counted twice)
InDegree of a vertex
Number of edges coming into the vertex
OutDegree of a vertex
Number of edges going out of the vertex
No of edges in a graph (HS theorem)
sum of degree of each vertex
terminal vertex(end vertex)
the vertex that the arrow is pointed too
Initial vertex
the vertex from which the arrow is pointed from
Complete Graph(Kn)
its a simple graph in which there is exactly one edge b/w each pair of distinct vertices in it
number of edges in kn
nC2 (n(n-1)/2)
Cycle (Cn)
It’s a path that starts from one vertex and ends at the same vertex
Wheel(Wn)
Obtained by adding a additional vertex to a cycle
Bipartite Graph
Its a graph in which the vertex set of v is partioned into 2 disjoint sets (v1 and v2) such that every edge in the graph connects a vertex in v1 and a vertex in v2 (making sure no edge in the graph connects to vertices of the same set aka v1 or v2).
Complete bipartite graph
its a bipartite graph in which each vertex in the set v1 connects to every vertex in the vertex set v2
Walk
its an alternating sequnce of vertices and connecting edges its the route from one vertex to another or from a vertex back to itself (vertices or edges can be repeated)
length of walk
number of edges in the walk
Trail
A walk that does not repeat any edges.
Path
A trail that does not repeat any vertices.
Cycle
A closed walk that does not repeat any edges.
Connected Graph
if there is a path b/w every pair of vertices in a graph
Disconnected
if there isnt a path b/w every pair of vertices in a graph
components
a disconnected graph consists of 2 or more connected graphs and each of these are called components
Regular Graph
If every vertex of a graph has the same degree then its called a regular graph
Subgraph
A graph H=(v1,e1) is called a subraph of G=(V,E) if v1 is a subset of V and e1 is a subset of E
Spanning subgraph
A graph H is called a spanning subgraph if v1=V and e1 is a subset of E aka have all vertices
Peterson Graph
graph with 10 vertices and 15 edges
Isomorphism graphs
graphs having same number of vertices edges and edge connectivity are called isomorphic graphs
disjoint subgraphs (edge/vertex)
2 subgraphs that have no (edges/ vertices) in common
vertex/edge deleted subgraph
litrally a set of vertex/edges are removed from the og graph
Adjacency matrix
a matrix which represents the adjacency of vertices in a graph
incidence matrix
a matrix which represnts the incidence of edges on a vertex
Euler Circuit
its a circuit that contains every edge of graph G
Euler path
its a simple path in a graph containing every edge of G
Hamiltonian circuit
Connected graph that is defined as a closed wal;k that traverse every vertice exactly once
Binary relation
its the cartesian product of AXB and is called binary relation R of A to B
semi in directed graphs
dont give a fuck about the arrows
Tree
its a Connected Acyclic graph im which one vertex is identified as its root and the edges are called branches
trvial
tree with a single vertex
how many paths does a tree have
One (there must be no more than one path b/w any 2 vertices )
Number of edges in a tree
number of vertices - 1
Forest
undirected disconnected acyclic graph such that each component of it is a tree
Null tree
a tree without edges is called a null tree
bridge
an edge that when removed disconnects the graph
Interior nodes
neither root or leaf nodes
height of root node(tree)
length of the longest path from root to leaf node
siblings(treee)
vertices with the same parent node
Path length of a tree
defined as the sum of the path lengths of the pendant vertices from the root
Distance (tree)
in a connected path the distance d(Vi ,Vj) between 2 vertics is the length of the shortest path
Center(tree)
vertex with the lowest excentricity
Eccentricity
its the farthest distance from a vertex to a pendant vertex in G
bi center(tree)
2 center vertices
m- ary tree
a rooted tree is called a m ary tree if every internal vertex has no more than m children
Spanning Tree
in a simple graph G a spanning tree of G is a sub graph of G that is a tree consisting of every vertex of G
Vertex connectivity
the min no of vertices to be removed such that the graph G gets disconnected
vertex connectivity of any complete graph
no of componenets = n-1
edge conectivity
min no of edges to be removed such that the graph G gets disconnected
seprable graph
a graph is said to be separable if its vertex connectivity is 1
fundamental cut set
if a edge in the cut set has a branch of a spanning tree in it then its called a fundamental cut set and rest are chords
fundamental circuit
when a chord is added to a spanning tree T and then forming a exactly one circuit that circuit is called a fundamental circuit
non separable
a graph that cant be disconnect by removing just one vertex
face of a graph
its the rejoin formed by a cycle on parallel edges or loops in G its also the region denoted as f
Jordan curve
non self intersecting continous closed curve in the planep
planar graph
if it can be re drawn on a plane without crossovers such a drawing is called planar embedding of G
embeddig of a graph
its the geometric representation of G drawn on a surface such that there is no crossovers
spherical embedding
on a sphere
Dual of a grtaph
The dual of a graph is a graph that is constructed by interchanging the roles of vertices and faces in the original graph. In other words, each vertex in the original graph becomes a face in the dual graph, and each face in the original graph becomes a vertex in the dual graph.
self dual graphs
a graph is said to be self dual if its isomophic to its own dual
properties of islolated matrix
each column hsa exactly 2 ones
no of ones in each row equals to the degree of the vertex
a row with 0s is for an isloated vertex
paralle edges provide identical columns
