Class work #9 and 10 -- Graph algorithms

[Akif Eyler]

Class work #9  (do NOT send me anything today)

Apr 30  First version of the project must be in your repo

==========================================

Graph algorithms

Consider the weighted graph G = (V, E) defined in the attached file
 
* Show that 3 colors are sufficient to color G
tutorialspoint.com/graph_theory/graph_theory_coloring.htm

* Find a minimum spanning tree in G -- is it unique?
https://www.wikiwand.com/en/Minimum_spanning_tree

* Find a shortest path from node a to node j

* Find a Hamiltonian circuit (cycle) in G

mathworld.wolfram.com/HamiltonianCycle.html

* Show that G does not contain an Eulerian circuit

mathworld.wolfram.com/EulerianCycle.html

* Modify G by adding an edge and removing an edge so that G' contains an Eulerian circuit

* Which problems cited above are NP-complete?

_Akif_Eyler_

[Akif Eyler]

G = (V, E) 

[Akif Eyler]

Bugün 11-13 arasında son sınıf çalışması yapılacak

Class work #10 -- cevabınızı saat 13'e kadar mail içinde gönderin

Ekteki dosyada tanımlanan G1 ve G2 için aşağıdaki soruları ayrı ayrı cevaplayın

* Decide if 3 colors are sufficient to color G

* Find a minimum spanning tree in G

* Find a Hamiltonian circuit (cycle) in G

* Decide if G contains an Eulerian circuit

_Akif_Eyler_

[Akif Eyler]

CW10 çözümü ekte -- finalde benzeri bir soru olacak

Cycle: path starting and ending at the same vertex (same as circuit)

Tree: graph with no cycle

Spanning tree: tree containing all vertices (no cycles)

Eulerian cycle goes through each edge once (all degrees must be even)

Hamiltonian cycle goes through each vertex once (no good algorithm)

---------
From: Celil Reha ESGICE
Date: Tue, May 7, 2019 at 12:34 PM
To: Akif Eyler 

1-) G1:3 colors are not enough               G2: 2 colors enough

2-) MST are shown 

3-) G1: Hamiltonian circuit is shown     G2: There is no Hamiltonian circuit

4-) G1: There is no Eulerian circuit        G2: Eulerian circuit is shown