graph theory

Question 1

capital of east prussia

Answer 1

Konigsberg aka Kaliningrad in Russia

Question 2

an island name _____ is in the middle of where the 2 rivers join

Answer 2

Kniephof

Question 3

who explained why crossing all7 bridges w/o crossing a bridge twice was impossible

Answer 3

Leonard Euler in 1736 presented the soln to the problem before the Russian academy

Question 4

it is a collection of points called vertices or nodes and line segments or curves called edged that connect the vertices

Answer 4

graph

Question 5

briefly explain what is vertices and edges in a graph

Answer 5

vertices: points
edges: line segments that connects the vertices

Question 6

define loop

Answer 6

an edge that connects a vertex to itself

Question 7

define multiple edges

Answer 7

if 2 vertices is connected by more than one edge

Question 8

define simple graph

Answer 8

graph with no loops and no multiple edges

Question 9

define the following
equivalent:
connected:
bridge:

Answer 9

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

Question 10

define path

Answer 10

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)

Question 11

what does it mean if a path begins and ends with the same vertex

Answer 11

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)

Question 12

define
adjacent:
degree:

Answer 12

adjacent: 2 vertices are adjacent if there is an edge joining them
degree: vertex is the no. of edges attached to it

Question 13

what do u call a graph that has a degree of each vertex is 0

Answer 13

null or disconnected graph

Question 14

define complete graph

Answer 14

has an edge connecting every pair of vertices (shld not contain multiple edges)
note: if every pair of vertices are adjacent = complete

Question 15

what is the formula of a complete graph with “n” vertices

Answer 15

refer to ppt
1/2n(n-1) for (n should be bigger than 3 or equal)

Question 16

it is a closed path that contains all the edges of the graph

Answer 16

Euler Graph
(circuit that covers all the edges ones)

Question 17

a graph that has an Euler circuit

Answer 17

Eulerian

Question 18

a connected graph is Eulerian if and only if each vertex has _____

Answer 18

even degree

Question 19

it is of a graph is a path that contains all the edges of the graph

Answer 19

Euler paths

Question 20

a graph has an Euler path if and only if exactly 2 of its vertices have _____

Answer 20

odd degree

Question 21

the euler path will begin and end with the _____

Answer 21

old-degree vertices

Question 22

difference between
Euler circuit -
Euler paths -

Answer 22

Euler circuit - each vertex has even degree
Euler paths -exactly 2 of its vertices have odd degree (basically start and end at the odd)

Question 23

briefly explain Euler’s theorem

Answer 23

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

Question 24

a Hamiltonian path of a graph is path passing through _____ of the graph ______

Answer 24

each vertex
exactly once

Question 25

if the Hamiltonian path is closed, it is called _____ aka ______

Answer 25

Hamiltonian cycle
Hamiltonian

Question 26

a complete graph with more than 2 vertices has a ______

Answer 26

Hamiltonian circuit

Question 27

2 Hamiltonian circuits are the same if they oaps through the same _____ in the same order, regardless of the vertex where they _____

Answer 27

vertices
begin and end

Question 28

define tree

Answer 28

any 2 vertices are connected to 1 path only

Question 29

properties of trees:

Answer 29

has no circuits
connected graphs
every edge in a tress is a bridge
tree with n vertices has exactly n-1 edges

Question 30

it is an undirected, disconnected, acyclic graph

Answer 30

forest

Question 31

a disjoint collection of tress

Answer 31

forest

Question 32

this tress is often finding the minimum total weight

Answer 32

minimum spanning trees

Question 33

what are the 2 algorithm to find the minimum spanning tree - briefly explain

Answer 33

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

Question 34

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

Answer 34

planar

Question 35

how to know if it is a planar graph

Answer 35

v + f = e + 2

v=vertices
f=face
e=edges

Question 36

how to do graph coloring

Answer 36

no same adjacent color
use smallest no. of colors

Question 37

the chromatic number of a planar graph is ____

Answer 37

4 (four-color theorem)

Question 37

why is graph coloring important
(give examples of graph coloring)

Answer 37

to assign diff colors to conflict things, we can separate them into diff grps
(scheduling problems
frequency allocation
to avoid conflicts)