unit 5 dm Flashcards
When are two vertices said to be adjacent/neighbours?
one edge between them atleast pic8
What is a null graph
no edges, all isolated vertexes
What is a trivial graph?
no edges and one vertices
What is a graph?
A collection of edges and vertices where the ordered pairs form edges
What does Graph G(V,E) represent?
V is an unempty set of vertices and E is a set of ordered pairs which represent edges
what does the therefore symbol represent (pic1)
null graph, 3 vertices
How is an edge represented?
a line, straight, curvy, long or short
Can the same graph be represented in diff ways? example?
pic2
How can graphs be classified?
finite: finite no. of edges and vertices
infinite: infinite no. of vertices
What are order and set and in which type of graph are the present?
In finite graph
OVSE
Order: no. of vertices
Set: no. of edges
(n,m) graph?
order -> n
size -> m
Graph(V,E) cardinality of V?
Set E cardinality?
|V| = order |E| = size
Null graph with n vertices representation?
(n,0) graph
How are finite graphs classified?
- Directed
direction associated with edge (ordered pair) - Undirected
no direction associated with edge (unordered pair)
What are end vertices?
Vi and Vj are vertices joined by edge ek then edge vertices are Vi, Vj of ek
Symbolically pic3
How are vertices and edges represented?
Vertices: V1, v2 (subscript)
OR
A,B,Cā¦
How are edges and edges represented?
e1, e2, e3..
or
AB, CD, ā¦
Can edges intersect and not form a vertex at intersection point
yes
pic5
even if one vertix diff, denoted as
distinct end verticespic5
self loop?
same vertex as end vertices
pic5
loop?
edges with same end vertices
diff directions
pic5
parallel edges
edges with same end vertices
same direction
pic5
multiple edges
2 or more edges with same end vertix pic 4
simple graph
no loops, no multiple edges
loop free graph
no loops
multigraph
no loops, yes multiple edges
general graph
yes loops, yes multiple edges
labeled graph
names are assigned to graph
unlabeled graph
no names assigned to graph
incidence
if there is an edge between A and B, A is incident on B pic 6
edge incident -> 2 vertices
vertix incident -> as many vertices
degree of vertices? in which graph type?
undirected
no. of vertices incident on a vertix (edges between how many vertices)
adjacent edge
non parallel edges with one common vertix
pic7
complete/full graph
order >= 2 (vertices) at least one edge between all vertices
denoted by k subscript n
(n = vertices)
n = 5, Kuratowskiās first graph pic9
bipartite graph
pic10
split into 2 disjoint sets V1 and V2
every edge connects vertex from V1 to vertex in V2
None only within V1 or within V2
complete bipartite
every v1 to every v2
pic 11, kurotowskis second graph
is complete bipartite, complete graph? why
no edge between same bipartite
How to check if bipartite?
assign 2 colors alternatively no adj same color
pic 12
Types of undirected simple graphs
complete
cycle: every vertex degree = 2
pic13
wheel: vertex connected to every other vertex(all degree 3 except center = vertex no. - 1)pic14
Types of graph
simple
multi
pseudo: self loops + maybe parallel edges
pic15
Directed graph
G(V,E)
u and v?
collection of ordered pairs
V -> nonempty set of vertices
E -> ordered set of edges
starting ->u, ending -> v
types of directed graphs
simple directed: no loops, no parallel edges
multi directed: parallel edges
pseudo/mixed directed:
directed + undirected edges
Union of graphs
G(V1,E1) union G(V2,E2) G(V,E) where V = v1 union V2 etc
pic 16
path/walk
seq of edges/vertices
circuit/closed walk
same initial and end point
simple path
each edge only once
adjacency and incidence
row,column = vertices row = vertices column = edges
deg(V) or d(v)
no. of edges join V vertices, loops 2x
degree sequence of graph
all degrees in non-ascending order
degree of graph
min deg(V) of graph
isolated vertex
not end vertix (deg(V) = 0)
pendant vertex
deg(V) = 1
pendant edge
edge from pendant vertex
regular graph of degree k/k-regular graph
all vertices, same degree, k
3 regular graph aka
cubic graph
Peterson graph
pic17
10 vertices, 15 edges
3d hypercube Q3
pic 18
k regular grapgh, 2^k vertices aka
k dimensional hypercube Qk
handshaking property
why does it work?
why called handshake?
aka
sum of all degrees = 2 * edges each edge counted twice (at each end) even no. of hanshakes obvio First Theorem of Graph theory pic 19 -> math form
Isomorphism
pic19 isomorphism reprsentation
f:V->Vā (f onto 1-1)
{A,B}->E {f(A),f(B)}->Eā
SAME ADJ MATRIX(rearrange columns)
SAME DEGREES
Same order, same size -> not need isomorphic
Subgraphs
g1 subgraph of g if:
all vertices and edges of g1 in g
edge in g1 same end vertices as g
g1 part of g
Subgraph results
all graphs subgraph of itself
graph n vertices sub of complete kn
single vertex in G1 sub G
single edge + end verices sub G
Spanning SubG
vertices in main
Induced SubG
vertices and edges in main
Edge/Vertex disjoint
both subs no common edge/no common edge and vertex
vertex disjoint -> edge disjoint
complement of subG
G - subG(G1) = comp of G1 in G
G - G1 or G1(bar)
G1(bar) = G triangle G1
walk classification
seq of vertixedge+
no. of edges -> length
vertix and edge more than once possible
how many paths of length n
A = adj matrix -> A^n paths
