Graph Theory Flashcards
When did graph theory start?
1736
Who proved that it’s impossible to walk such a
path?
Leonhard Eulers
A branch of mathematics that illustrates and analyzes connections
such as these
Graph theory
a set of points
Vertices
line segments or curves
Edges
an edge, the endpoints of which are the same vertex
Loop
a graph can be thought of as a movement from one vertex to another
Path
If a path ends at the same vertex at which it started
Closed path
A circuit that uses every edge but never uses the same edge twice
Eulers circuit
The number of edges that meet at a vertex
Degree of vertex
A graph that has an Euler’s circuit
Eulerian
A path that begins and ends at the same vertex and passes through each vertex of a graph exactly once
Hamiltonian Circuit
A graph that contains Hamiltonian circuit
Hamiltonian
If every vertex has degree of at least n/2
Dirac’s theorem
a graph in which each edge is associated with a value
Weighted graph
is so called because it has us choose the “cheapest” option at every chance we get
Greedy algorithm
If the graph is drawn in such a way that no edges cross
Planar drawing
the edges divide the graph into different regions
Faces
The region surrounding the graph, or the exterior
Infinite face
Euler’s formula
Vertices + Faces = Edges + 2
Every planar graph has 4-colorable
Four color theorem
The minimum number of colors needed to color a graph so that no edge connects vertices of the same color
Chromatic number of a graph
29=8 mod 3
29-8/3 = 21/3 (7 an integer )
