of 106

# Prestation_ClydeShen

Published on: Mar 4, 2016

#### Transcripts - Prestation_ClydeShen

• 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