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
if the Hamiltonian path is closed, it is called _____ aka ______
Hamiltonian cycle
Hamiltonian
a complete graph with more than 2 vertices has a ______
Hamiltonian circuit
2 Hamiltonian circuits are the same if they oaps through the same _____ in the same order, regardless of the vertex where they _____
vertices
begin and end
define tree
any 2 vertices are connected to 1 path only
properties of trees:
has no circuits
connected graphs
every edge in a tress is a bridge
tree with n vertices has exactly n-1 edges
it is an undirected, disconnected, acyclic graph
forest
a disjoint collection of tress
forest
this tress is often finding the minimum total weight
minimum spanning trees
what are the 2 algorithm to find the minimum spanning tree - briefly explain
prim’s algorithm:
vertex chosen at random
find all edges that connect the tree to new vertices with minimum no.
kruskal’s algorithm:
sort all edges from low to high
take edge with lowest weight
a graph is ____ if it can be drawn in such a way that no edges cross. this means that any 2 edges can meet only at an endpoint
planar
how to know if it is a planar graph
v + f = e + 2
v=vertices
f=face
e=edges
how to do graph coloring
no same adjacent color
use smallest no. of colors
the chromatic number of a planar graph is ____
4 (four-color theorem)
why is graph coloring important
(give examples of graph coloring)
to assign diff colors to conflict things, we can separate them into diff grps
(scheduling problems
frequency allocation
to avoid conflicts)
