Published on: **Mar 4, 2016**

- 1. GRAPH COLOURING ON GRAPH DYNAMICIAL SYSTEM Clyde Shen Supervisor by: Dr. Jiamou Liu
- 2. Overview • Graph Theory – Graph – Graph Colouring • Automaton – deterministic finite automaton (DFA) • Graph Dynamical System – Graph-cellular Automaton – Some specific case: linear graph, circle graph, tree graph, wheel graph and Peterson graph
- 3. Graph Theory
- 4. Graph Theory Leonhard Paul Euler (1707- 1783) : a pioneering Swiss mathematician • Mathematical notation • Analysis • Number theory • Graph Theory • Applied mathematics • Physics and Astronomy • Logic The Seven Bridges of Königsberg : Is it possible to take a walk through town, starting and ending at the same place, and cross each bridge exactly once?
- 5. Graph Theory
- 6. Graph Theory What is a Graph?
- 7. Graph Theory What is a Graph?
- 8. Graph Theory What is a Graph?
- 9. Graph Theory What is a Graph?
- 10. Graph Theory What is a Graph?
- 11. Graph Theory Graph 𝐺 = (𝑉, 𝐸) 𝑉 is a finite set of vertices 𝐸 is a finite set of edges V = {1,2,3,4,5} E = { {1, 4}, {2, 4}, {3, 5}, {4, 5}, {2, 5} }
- 12. Graph Theory Graph 𝐺 = (𝑉, 𝐸) 𝑉 is a finite set of vertices 𝐸 is a finite set of edges Undirected Graph Directed Graph
- 13. Graph Theory • Undirected Graph • Planar Graph – a graph can be drawn on a plane surface – No two edges intersect
- 14. Graph Theory • Undirected Graph • Planar Graph – a graph can be drawn on a plane surface – No two edges intersect
- 15. Graph Theory • Undirected Graph • Planar Graph – a graph can be drawn on a plane surface – No two edges intersect
- 16. Graph Theory • Undirected Graph • Planar Graph – a graph can be drawn on a plane surface – No two edges intersect • Graph Colouring
- 17. Graph Theory Graph Colouring Problem: • 𝐺 = (𝑉, 𝐸) • set 𝐶 is a function 𝑓 ∶ 𝑉 → 𝐶, where 𝐶 is a set of colors • ∀𝑖,𝑗 : 𝑣𝑖, 𝑣𝑗 ∈ 𝐸 ⇒ 𝑓(𝑣𝑖) ≠ 𝑓(𝑣𝑗)
- 18. Graph Theory
- 19. Graph Theory 𝐶 = 4
- 20. Graph Theory 𝐶 = 4 𝐶 = 2
- 21. Graph Theory • The chromatic number of a graph 𝐺 is the size of a smallest set 𝐶 for there is a proper colouring of G with 𝐶 • denoted by 𝜒(𝐺) • If 𝜒 𝐺 ≤ 𝑘 , 𝐺 is k-colourable
- 22. Graph Theory • Computational complexity – Graph colouring is NP-complete – NP-hard to compute the chromatic number – Goal: design efficient algorithm for finding colouring using ≥ 𝜒(𝐺) colours
- 23. Graph Theory • Algorithms for colouring
- 24. Graph Theory • Algorithms for colouring – Greedy colouring http://en.wikipedia.org/wiki/Greedy_coloring – Parallel and distributed algorithms Schnitger, G. (2009). Parallel and Distributed Algorithms. Algorithms, 10.
- 25. Automaton
- 26. Automaton • Deterministic finite automaton (DFA) – DFA is a 5-tuple (𝑄, 𝛴, 𝛿, 𝑞0 , 𝐹) • Q is a finite set of states • 𝛴 is a finite set of input symbols called the alphabet • 𝛿 is transition function (𝛿: 𝑄 × 𝛴 → 𝑄) • 𝑞0 is start state(𝑞0 ∈ 𝑄) • 𝐹 is set of accepting states (𝐹 ⊆ 𝑄)
- 27. Automaton • Deterministic finite automaton (DFA) – DFA is a 5-tuple (𝑄, 𝛴, 𝛿, 𝑞0 , 𝐹) – Example of a DFA 𝑀 = (𝑄, 𝛴, 𝛿, 𝑞0 , 𝐹) • 𝑄 = {𝑆1, 𝑆2} • 𝛴 = {0,1} • 𝑞0 = 𝑆1 • 𝐹 = {𝑆1} • 𝛿 is defined by the following state transition table: 0 1 𝑆1 𝑆2 𝑆1 𝑆2 𝑆1 𝑆2
- 28. +
- 29. Graph Dynamical System
- 30. Graph Dynamical System • Let a graph 𝐺 = 𝑉, 𝐸 be a undirected graph – ∀ 𝑣 ∈ 𝑉, denote the set of neighbours by ℕ(v) – Vertex has no more than 𝑑 𝑔 neighbours. • A local orientation ∆ is a function 𝜇 ∶ 𝑉 × {1,2, … , 𝑑 𝑔} → (𝑉 ∪ {□}) where □ ∉𝑉 ∀ 𝑣 ∈ 𝑉 we have rules:
- 31. Graph Dynamical System • Graph-cellular Automaton (GA)
- 32. Graph Dynamical System • Graph-cellular Automaton (GA) 𝔄 is a 4-tuple 𝔄 = (𝑄, 𝑞0, ∆, 𝜇) consisting of – Q is a finite set of states. – q0 is a quiescent state. – ∆: 𝑄 × (𝑄 ∪ {□}) 𝑑 𝑔→ 𝑄 is the local transition. – 𝜇 is a local orientation of graph
- 33. Graph Dynamical System • Graph-cellular Automaton (GA) 𝔄 is a 4-tuple 𝔄 = (𝑄, 𝑞0, ∆, 𝜇) consisting of – Q is a finite set of states. – q0 is a quiescent state. – ∆: 𝑄 × (𝑄 ∪ {□}) 𝑑 𝑔→ 𝑄 is the local transition. – 𝜇 is a local orientation of graph quiescent state : ∆ 𝑞0, 𝑞1, 𝑞2, … , 𝑞 𝑑 𝑔 = 𝑞0 if 𝑞1, 𝑞2, … , 𝑞 𝑑 𝑔 ∈ {𝑞0, □}
- 34. Graph Dynamical System Dead vertex Alive vertex Alive vertex
- 35. Graph Dynamical System • Basic local transition rule: – ∀ 𝑣∈ 𝑉: ∆ 𝑞 𝑣, 𝑞1, 𝑞2, … , 𝑞 𝑑 𝑔 = 𝑞′ 𝑣 where 𝑞𝑞 𝑣 = min(𝑞 𝑣, 𝑞𝑞 𝑣)
- 36. Graph Dynamical System • Basic local transition rule: – ∀ 𝑣∈ 𝑉: ∆ 𝑞 𝑣, 𝑞1, 𝑞2, … , 𝑞 𝑑 𝑔 = 𝑞′ 𝑣 where 𝑞𝑞 𝑣 = min(𝑞 𝑣, 𝑞𝑞 𝑣) (1) (2)
- 37. Graph Dynamical System For example: • Linear graph
- 38. Graph Dynamical System For example: • Linear graph – Odd number of vertex – Even number of vertex
- 39. Graph Dynamical System Odd number of vertex:
- 40. Graph Dynamical System Odd number of vertex:
- 41. Graph Dynamical System Odd number of vertex:
- 42. Graph Dynamical System Odd number of vertex:
- 43. Graph Dynamical System Odd number of vertex:
- 44. Graph Dynamical System Odd number of vertex:
- 45. Graph Dynamical System Odd number of vertex:
- 46. Graph Dynamical System Odd number of vertex:
- 47. Graph Dynamical System Odd number of vertex:
- 48. Graph Dynamical System Odd number of vertex: Done!
- 49. Graph Dynamical System Even number of vertex:
- 50. Graph Dynamical System Even number of vertex:
- 51. Graph Dynamical System Even number of vertex:
- 52. Graph Dynamical System Even number of vertex:
- 53. Graph Dynamical System Even number of vertex:
- 54. Graph Dynamical System Even number of vertex:
- 55. Graph Dynamical System Even number of vertex:
- 56. Graph Dynamical System Even number of vertex:
- 57. Graph Dynamical System Even number of vertex:
- 58. Graph Dynamical System Even number of vertex:
- 59. Graph Dynamical System Even number of vertex: Done!
- 60. Graph Dynamical System • Linear graph
- 61. Graph Dynamical System • Linear graph • Circle graph – Even number of vertex – Odd number of vertex
- 62. Graph Dynamical System Even number of vertex:
- 63. Graph Dynamical System Even number of vertex:
- 64. Graph Dynamical System Even number of vertex:
- 65. Graph Dynamical System Even number of vertex:
- 66. Graph Dynamical System Even number of vertex:
- 67. Graph Dynamical System Even number of vertex:
- 68. Graph Dynamical System Even number of vertex:
- 69. Graph Dynamical System Even number of vertex: Done!
- 70. Graph Dynamical System Odd number of vertex:
- 71. Graph Dynamical System Odd number of vertex:
- 72. Graph Dynamical System Odd number of vertex:
- 73. Graph Dynamical System Odd number of vertex:
- 74. Graph Dynamical System Odd number of vertex:
- 75. Graph Dynamical System Odd number of vertex:
- 76. Graph Dynamical System Odd number of vertex: Loop!
- 77. Graph Dynamical System • Linear graph • Circle graph • Tree graph
- 78. Graph Dynamical System Tree graph:
- 79. Graph Dynamical System Tree graph:
- 80. Graph Dynamical System Tree graph:
- 81. Graph Dynamical System Tree graph:
- 82. Graph Dynamical System Tree graph:
- 83. Graph Dynamical System Tree graph: Done!
- 84. Graph Dynamical System • Linear graph • Circle graph • Tree graph • Wheel graph
- 85. Graph Dynamical System Wheel Graph:
- 86. Graph Dynamical System Wheel Graph:
- 87. Graph Dynamical System Wheel Graph:
- 88. Graph Dynamical System Wheel Graph:
- 89. Graph Dynamical System Wheel Graph:
- 90. Graph Dynamical System Wheel Graph:
- 91. Graph Dynamical System Wheel Graph: Loop!
- 92. Graph Dynamical System • Linear graph • Circle graph • Tree graph • Wheel graph • Peterson graph
- 93. Graph Dynamical System Peterson graph:
- 94. Graph Dynamical System Peterson graph:
- 95. Graph Dynamical System Peterson graph:
- 96. Graph Dynamical System Peterson graph:
- 97. Graph Dynamical System Peterson graph:
- 98. Graph Dynamical System Peterson graph:
- 99. Graph Dynamical System Peterson graph: Loop!
- 100. Graph Dynamical System • Linear graph • Circle graph • Tree graph • Wheel graph • Peterson graph
- 101. Conclusion
- 102. Conclusion Result: INPUT: OUTPUT: Graph-cellular Automaton + Rules
- 103. Conclusion • Graph Theory – Graph: planar graph – Graph Colouring: chromatic number • Automaton – deterministic finite automaton (DFA) • Graph Dynamical System – Graph-cellular Automaton – Some specific case: linear graph, circle graph, tree graph, wheel graph and Peterson graph
- 104. Conclusion • Initialize the use of graph dynamical system (graph-cellular automaton) • Graph-cellular automaton can be used as a viable tool in obtaining a colouring for specific classes of graph • Extend this work to more general classes of graph
- 105. Questions?
- 106. THANK YOU