Graph Theory Flashcards
Kruskal’s Algorithm
start from smallest weight and continue with smallest weights
Minimal Spanning Tree
spanning tree with smallest total weight
Nearest-Neighbor Algorithm
1) start with any vertex
2) find the vertex that is closest to the previous vertex and visit it
3) make sure that a vertex is not visited more than once
-in general, does not provide optimal solution
Circuit
path with same initial and final point
Euler Circuit
all edges are visited exactly once
-each vertex has even degrees
Degree
number of edges touching one point
Euler’s Theorem
a connected graph has a Euler circuit provided all its vertices has even degrees
Hamilton Circuit
each vertex is visited exactly once
Hamilton Circuit Formula
(n-1)!
n = number of vertices
the number of distinct Hamiltonian circuits in a complete graph with “n” vertices
Complete Graph
all vertices are connected by an edge
TSP
Traveling Salesman Problem
visit each vertex exactly once and end up where he started
Hamilton Circuit
in general, no solution unless it is a complete graph
Euler’s Formula
V-E+F=2
any connected graph
Regular Solid
Platonic Solid
3D shape satisfying each face is the same regular polygon
same number of polygons meet each vertex
Platonic Solids (5)
Vertices Edges Faces
1) Tetrahedron 4 6 4
2) Octahedron 6 12 8
3) Hexahedron 8 12 6
4) Dodecahedron 20 30 12
5) Icosahedron 12 30 20
Planar Graph
a graph that can be redrawn so no edges touch each other
not possible if k5 or k3,3
