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
