Please enable JavaScript.
Coggle requires JavaScript to display documents.
Topic 4: Graph Theory - Coggle Diagram
Topic 4: Graph Theory
-
Hamilton Path & Cycle
-
-
DIRAC's Theorem
- simple graph with vertices n >= 3
- deg(v) >= n/2 for each vertex
ORE's Theorem
- simple graph with n>= 3 vertices
- deg(v) + deg(w) >= n
- non-adjacent vertices v and w
Tree
-
Rooted Tree
Binary Tree
Degree of vertex
-
deg(u) = 2, deg(v) = 3, deg(w) = 4, deg(z) =1
simple path and cycle
simple cycle:
- start and end at the same vertex
- without repeated edges
simple path:
- a path without repeated edges
Matrices
Adjacency matrix:
- rows and columns represent edges
Incidence matrix:
- Rows represent vertices, columns represent edges
-
Definition of graph
A graph G = (V,E)
where
V = set of vertices
E = set of pairs, called edges
-
-
-
-