Final Flashcards
A vertex set ๐
A collection of points,vertices are dots,
An edge set ๐ธ
A collection of unordered pairs of vertices representing connections between them
edges are lines connecting these dots.
A walk from vertex
๐ฃ1To ๐ฃ๐
โ
is a sequence of edges
{V1,V2}{V2,V3},โฆ{Vn-1,Vn}
A circuit is a walk where the start and end vertices are the same:
A circuit is a walk where the start and end vertices are the same:
V1=Vn
A path
is a walk in which no vertex is revisited
Vi/=Vj for all i and j
Cycle:
A cycle is a special type of circuit with these properties:
It starts and ends at the same vertex (๐ฃ
1
=
๐ฃ
๐
v
1
โ
=v
n).
A walk vs A path
A walk may revisit vertices and edges, while a path cannot revisit vertices.
A circuit and a cycle
A circuit revisits the starting vertex and has a direction, while a cycle is undirected and only revisits the start/end vertex.
A path from x to y is a walk in G that has no repeated veritices
A path from x to y is a walk in G that has no repeated veritices
A trail from x to y is an open walk in G in which each edge appears no more than it multiplicity
A trail from x to y is an open walk in G in which each edge appears no more than it multiplicity
A circuit from x to x is a closed walk in G in which each edge appears no more than its multiplicity
A circuit from x to x is a closed walk in G in which each edge appears no more than its multiplicity
Euler Trail
Visit every edge exactly one, doesnโt necessarily start and end at the same vertex
The graph must be connected
Has exactly 2 vertices must have an odd degree
Euler circuit
Visit every edge once
Starts and ends at the same vertex
Graphs must be connected
Vertices have an even degree
Let G(V, E) be a multi-graph
G is a tree if G is connected and does not contain a cycle
G is a forest if G does not contain a cycle (every component of a forest is a tree)
A vertex of deg 1 is called a leaf or pendant vertex
If T=(V, E) is a tree with leaf v the T-v is a tree
If T=(V, E) is a tree with leaf v the T-v is a tree
If T=(V, E) is a tree and u, vโ V are distinct, there is a unique path in T with ends u,v
If T=(V, E) is a tree and u, vโ V are distinct, there is a unique path in T with ends u,v
Main properties of tree
If T= (V, E) is a tree the |V|=|E|+1
If G=(V,E) is a forest with K trees then |V|=|E|+K
If G=(V, E) satisfies|V|=|E|+1 then G must have a vertex of deg 0 or at least two degrees of 1
If G=(V, E) satisfies|V|=|E|+1 then G must have a vertex of deg 0 or at least two degrees of 1
Every tree T=(V, E) with |V|>2 has at least 2 leaves
Every tree T=(V, E) with |V|>2 has at least 2 leaves
Deg sum formla
ฮฃdeg(V)=2.|E|
Characterization of trees
let G=(V, E) be a multigraph
- G is connected and has no cycle
- G is connected and |V|=|E|+1
- G has no cycle and |V|=|E|+1
- There is a unique path between every pair of vertices in G
Bipartite graph
if we can partition the vertices into 2 non-empty subset V1 and V2 such that
1) V1^V2=DNE
2) V1vV2=v
3) every edge in E is incident with one vertex in V1 and one vertex in V2
Km,n
|V1|=n and |V2|=m
of edges = n.m
How many edges are in a path on n vertices
n-1
How many edges are in a cycle on n vertices
n
How many edges are in Kn?
nC2
How many edges are in Km,n?
n.m
How many graphs are there with vertices {1,โฆn}?
We can choose from nC2 edgesโ->
How many graphs have n vertices and m edges?
(nC2)Cm
Let V1 and V2 be disjoint with |V1|=n1 and |V2|=n2
how many graphs have bipartition (V1, V2)?
2^(n1.n2)
Let V1 and V2 be disjoint with |V1|=n1 and |V2|=n2
how many graphs have bipartition (V1, V2) with m edges?
(n1.n2) C m
How many spanning subgraphs do Kn1, n2 have?
2^(n1.n2)
How many spanning subgraphs do Kn1,n2 have exactly m edges?
(n1.n2) C m
induced subgraph
If G=(V, E) is a graph with |V|=n, how many induced subgraphs does G have?
Guess 2^n, correct!
An induced subgraph is determined by the vertex VโcC and 2 different Vโ give different subgraphs.
of subsets Vโ is a subset of V is indeed 2^n
