graph theory Flashcards
capital of east prussia
Konigsberg aka Kaliningrad in Russia
an island name _____ is in the middle of where the 2 rivers join
Kniephof
who explained why crossing all7 bridges w/o crossing a bridge twice was impossible
Leonard Euler in 1736 presented the soln to the problem before the Russian academy
it is a collection of points called vertices or nodes and line segments or curves called edged that connect the vertices
graph
briefly explain what is vertices and edges in a graph
vertices: points
edges: line segments that connects the vertices
define loop
an edge that connects a vertex to itself
define multiple edges
if 2 vertices is connected by more than one edge
define simple graph
graph with no loops and no multiple edges
define the following
equivalent:
connected:
bridge:
equivalent: same vertices connected in the same way
connected: if any 2 vertices, there is at least on path that joins them
bridge: is an edge that when you remove makes the graph disconnected
define path
it is an alternating sequences of vertices and edges.
it can be seen as a trip from one vertex to another using edges of a graph
(see example in ppt - no repeated vertices)
what does it mean if a path begins and ends with the same vertex
it is closed path or a circuit/ cycle
(ex: a >b >c >d >h >g >f >a
since it has a length of 7 = 7-cycle)
define
adjacent:
degree:
adjacent: 2 vertices are adjacent if there is an edge joining them
degree: vertex is the no. of edges attached to it
what do u call a graph that has a degree of each vertex is 0
null or disconnected graph
define complete graph
has an edge connecting every pair of vertices (shld not contain multiple edges)
note: if every pair of vertices are adjacent = complete
what is the formula of a complete graph with “n” vertices
refer to ppt
1/2n(n-1) for (n should be bigger than 3 or equal)
it is a closed path that contains all the edges of the graph
Euler Graph
(circuit that covers all the edges ones)
a graph that has an Euler circuit
Eulerian
a connected graph is Eulerian if and only if each vertex has _____
even degree
it is of a graph is a path that contains all the edges of the graph
Euler paths
a graph has an Euler path if and only if exactly 2 of its vertices have _____
odd degree
the euler path will begin and end with the _____
old-degree vertices
difference between
Euler circuit -
Euler paths -
Euler circuit - each vertex has even degree
Euler paths -exactly 2 of its vertices have odd degree (basically start and end at the odd)
briefly explain Euler’s theorem
for connected graph:
1. all vertices r even degree= have at least 1 Euler circuit
2. two vertices are odd degree = Euler path
3. more than 2 odd degree vertices = no Euler path nor circuits
a Hamiltonian path of a graph is path passing through _____ of the graph ______
each vertex
exactly once
