尊敬的 微信汇率:1円 ≈ 0.046166 元 支付宝汇率:1円 ≈ 0.046257元 [退出登录]
SlideShare a Scribd company logo
Coloring Graphs
This handout:
• Coloring maps and graphs
• Chromatic number
• Applications of graph coloring
Coloring maps
• Color a map such that two regions with a common border
are assigned different colors.
• Each map can be represented by a graph:
– Each region of the map is represented by a vertex;
– Edges connect two vertices if the regions represented by these
vertices have a common border.
• The resulting graph is called the dual graph of the map.
Coloring Graphs
• Definition: A graph has been colored if a color has
been assigned to each vertex in such a way that
adjacent vertices have different colors.
• Definition: The chromatic number of a graph is the
smallest number of colors with which it can be
colored.
In the example above, the chromatic number is 4.
Coloring Planar Graphs
• Definition: A graph is planar if it can be
drawn in a plane without edge-crossings.
• The four color theorem: For every planar
graph, the chromatic number is ≤ 4.
Was posed as a conjecture in the 1850s. Finally proved in
1976 (Appel and Haken) by the aid of computers.
An application of graph coloring in scheduling
Twelve faculty members in a mathematics department serve on the
following committees:
 Undergraduate education: Sineman, Limitson, Axiomus, Functionini
 Graduate Education: Graphian, Vectorades, Functionini, Infinitescu
 Colloquium: Lemmeau, Randomov, Proofizaki
 Library: Van Sum, Sineman, Lemmeau
 Staffing: Graphian, Randomov, Vectorades, Limitson
 Promotion: Vectorades, Van Sum, Parabolton
The committees must all meet during the first week of classes, but
there are only three time slots available. Find a schedule that will
allow all faculty members to attend the meetings of all committees
on which they serve.
An application of graph coloring in exam scheduling
Suppose that in a particular quarter there are students taking each of the
following combinations of courses:
 Math, English, Biology, Chemistry
 Math, English, Computer Science, Geography
 Biology, Psychology, Geography, Spanish
 Biology, Computer Science, History, French
 English, Psychology, Computer Science, History
 Psychology, Chemistry, Computer Science, French
 Psychology, Geography, History, Spanish
What is the minimum number of examination periods required for
the exams in the ten courses specified so that students taking any
of the given combinations of courses have no conflicts? Find a
schedule that uses this minimum number of periods.
An application of graph coloring in exam scheduling
Suppose that in a particular quarter there are students taking each of the
following combinations of courses:
 Math, English, Biology, Chemistry
 Math, English, Computer Science, Geography
 Biology, Psychology, Geography, Spanish
 Biology, Computer Science, History, French
 English, Psychology, Computer Science, History
 Psychology, Chemistry, Computer Science, French
 Psychology, Geography, History, Spanish
What is the minimum number of examination periods required for
the exams in the ten courses specified so that students taking any
of the given combinations of courses have no conflicts? Find a
schedule that uses this minimum number of periods.

More Related Content

What's hot

Chromatic Number of a Graph (Graph Colouring)
Chromatic Number of a Graph (Graph Colouring)Chromatic Number of a Graph (Graph Colouring)
Chromatic Number of a Graph (Graph Colouring)
Adwait Hegde
 
Unit 1 chapter 1 Design and Analysis of Algorithms
Unit 1   chapter 1 Design and Analysis of AlgorithmsUnit 1   chapter 1 Design and Analysis of Algorithms
Unit 1 chapter 1 Design and Analysis of Algorithms
P. Subathra Kishore, KAMARAJ College of Engineering and Technology, Madurai
 
Graph Coloring : Greedy Algorithm & Welsh Powell Algorithm
Graph Coloring : Greedy Algorithm & Welsh Powell AlgorithmGraph Coloring : Greedy Algorithm & Welsh Powell Algorithm
Graph Coloring : Greedy Algorithm & Welsh Powell Algorithm
Priyank Jain
 
Backtracking
Backtracking  Backtracking
Backtracking
Vikas Sharma
 
Graph Coloring
Graph ColoringGraph Coloring
Graph Coloring
Dr. Abdul Ahad Abro
 
Graph Coloring and Its Implementation
Graph Coloring and Its ImplementationGraph Coloring and Its Implementation
Graph Coloring and Its Implementation
IJARIIT
 
Graph Theory: Trees
Graph Theory: TreesGraph Theory: Trees
Graph Theory: Trees
Ashikur Rahman
 
Graph coloring Algorithm
Graph coloring AlgorithmGraph coloring Algorithm
Graph coloring Algorithm
আদনান ফিরোজ
 
Depth First Search ( DFS )
Depth First Search ( DFS )Depth First Search ( DFS )
Depth First Search ( DFS )
Sazzad Hossain
 
Dijkstra s algorithm
Dijkstra s algorithmDijkstra s algorithm
Dijkstra s algorithm
mansab MIRZA
 
Dfs presentation
Dfs presentationDfs presentation
Dfs presentation
Alizay Khan
 
Edge Coloring & K-tuple coloring
Edge Coloring & K-tuple coloringEdge Coloring & K-tuple coloring
Edge Coloring & K-tuple coloring
Dr. Abdul Ahad Abro
 
Graph coloring using backtracking
Graph coloring using backtrackingGraph coloring using backtracking
Graph coloring using backtracking
shashidharPapishetty
 
A presentation on prim's and kruskal's algorithm
A presentation on prim's and kruskal's algorithmA presentation on prim's and kruskal's algorithm
A presentation on prim's and kruskal's algorithm
Gaurav Kolekar
 
Backtracking
BacktrackingBacktracking
Backtracking
Pranay Meshram
 
CS6702 Unit III coloring ppt
CS6702   Unit III coloring pptCS6702   Unit III coloring ppt
CS6702 Unit III coloring ppt
Abilaasha Ganesan
 
Euler graph
Euler graphEuler graph
Euler graph
AAQIB PARREY
 
Our presentation on algorithm design
Our presentation on algorithm designOur presentation on algorithm design
Our presentation on algorithm design
Nahid Hasan
 
Greedy algorithm
Greedy algorithmGreedy algorithm
Sum of subsets problem by backtracking 
Sum of subsets problem by backtracking Sum of subsets problem by backtracking 
Sum of subsets problem by backtracking 
Hasanain Alshadoodee
 

What's hot (20)

Chromatic Number of a Graph (Graph Colouring)
Chromatic Number of a Graph (Graph Colouring)Chromatic Number of a Graph (Graph Colouring)
Chromatic Number of a Graph (Graph Colouring)
 
Unit 1 chapter 1 Design and Analysis of Algorithms
Unit 1   chapter 1 Design and Analysis of AlgorithmsUnit 1   chapter 1 Design and Analysis of Algorithms
Unit 1 chapter 1 Design and Analysis of Algorithms
 
Graph Coloring : Greedy Algorithm & Welsh Powell Algorithm
Graph Coloring : Greedy Algorithm & Welsh Powell AlgorithmGraph Coloring : Greedy Algorithm & Welsh Powell Algorithm
Graph Coloring : Greedy Algorithm & Welsh Powell Algorithm
 
Backtracking
Backtracking  Backtracking
Backtracking
 
Graph Coloring
Graph ColoringGraph Coloring
Graph Coloring
 
Graph Coloring and Its Implementation
Graph Coloring and Its ImplementationGraph Coloring and Its Implementation
Graph Coloring and Its Implementation
 
Graph Theory: Trees
Graph Theory: TreesGraph Theory: Trees
Graph Theory: Trees
 
Graph coloring Algorithm
Graph coloring AlgorithmGraph coloring Algorithm
Graph coloring Algorithm
 
Depth First Search ( DFS )
Depth First Search ( DFS )Depth First Search ( DFS )
Depth First Search ( DFS )
 
Dijkstra s algorithm
Dijkstra s algorithmDijkstra s algorithm
Dijkstra s algorithm
 
Dfs presentation
Dfs presentationDfs presentation
Dfs presentation
 
Edge Coloring & K-tuple coloring
Edge Coloring & K-tuple coloringEdge Coloring & K-tuple coloring
Edge Coloring & K-tuple coloring
 
Graph coloring using backtracking
Graph coloring using backtrackingGraph coloring using backtracking
Graph coloring using backtracking
 
A presentation on prim's and kruskal's algorithm
A presentation on prim's and kruskal's algorithmA presentation on prim's and kruskal's algorithm
A presentation on prim's and kruskal's algorithm
 
Backtracking
BacktrackingBacktracking
Backtracking
 
CS6702 Unit III coloring ppt
CS6702   Unit III coloring pptCS6702   Unit III coloring ppt
CS6702 Unit III coloring ppt
 
Euler graph
Euler graphEuler graph
Euler graph
 
Our presentation on algorithm design
Our presentation on algorithm designOur presentation on algorithm design
Our presentation on algorithm design
 
Greedy algorithm
Greedy algorithmGreedy algorithm
Greedy algorithm
 
Sum of subsets problem by backtracking 
Sum of subsets problem by backtracking Sum of subsets problem by backtracking 
Sum of subsets problem by backtracking 
 

Viewers also liked

Graph Theory,Graph Terminologies,Planar Graph & Graph Colouring
Graph Theory,Graph Terminologies,Planar Graph & Graph ColouringGraph Theory,Graph Terminologies,Planar Graph & Graph Colouring
Graph Theory,Graph Terminologies,Planar Graph & Graph Colouring
Saurabh Kaushik
 
Algorithms for Graph Coloring Problem
Algorithms for Graph Coloring ProblemAlgorithms for Graph Coloring Problem
Algorithms for Graph Coloring Problem
Shengyi Wang
 
Graph T
Graph TGraph T
Marketing analytics alpesh doshi social network analysis - using social gra...
Marketing analytics alpesh doshi   social network analysis - using social gra...Marketing analytics alpesh doshi   social network analysis - using social gra...
Marketing analytics alpesh doshi social network analysis - using social gra...
Alpesh Doshi
 
FOSDEM 2014: Social Network Benchmark (SNB) Graph Generator
FOSDEM 2014:  Social Network Benchmark (SNB) Graph GeneratorFOSDEM 2014:  Social Network Benchmark (SNB) Graph Generator
FOSDEM 2014: Social Network Benchmark (SNB) Graph Generator
LDBC council
 
Overview of research in chemistry
Overview of research in chemistryOverview of research in chemistry
Overview of research in chemistry
Anuradha Verma
 
THE APPLICATION OF CAUSE EFFECT GRAPH FOR THE COLLEGE PLACEMENT PROCESS
THE APPLICATION OF CAUSE EFFECT GRAPH FOR THE COLLEGE PLACEMENT PROCESSTHE APPLICATION OF CAUSE EFFECT GRAPH FOR THE COLLEGE PLACEMENT PROCESS
THE APPLICATION OF CAUSE EFFECT GRAPH FOR THE COLLEGE PLACEMENT PROCESS
VESIT/University of Mumbai
 
Graph theory Application
Graph theory ApplicationGraph theory Application
Graph theory Application
Sultan Mehmood
 
Spherule Diagrams with Graph for Social Network Visualization
Spherule Diagrams with Graph for Social Network VisualizationSpherule Diagrams with Graph for Social Network Visualization
Spherule Diagrams with Graph for Social Network Visualization
Mithileysh Sathiyanarayanan
 
burton_discrete_graph theory
burton_discrete_graph theoryburton_discrete_graph theory
burton_discrete_graph theory
guest63f42b
 
Multi-perspective Visualisation Approach for E-discovery Email Investigation
Multi-perspective Visualisation Approach for E-discovery Email InvestigationMulti-perspective Visualisation Approach for E-discovery Email Investigation
Multi-perspective Visualisation Approach for E-discovery Email Investigation
Mithileysh Sathiyanarayanan
 
Data Mining Seminar - Graph Mining and Social Network Analysis
Data Mining Seminar - Graph Mining and Social Network AnalysisData Mining Seminar - Graph Mining and Social Network Analysis
Data Mining Seminar - Graph Mining and Social Network Analysis
vwchu
 
Graphs - CH10 - Discrete Mathematics
Graphs - CH10 - Discrete MathematicsGraphs - CH10 - Discrete Mathematics
Graphs - CH10 - Discrete MathematicsOmnia A. Abdullah
 
Application of graph theory in drug design
Application of graph theory in drug designApplication of graph theory in drug design
Application of graph theory in drug design
Reihaneh Safavi
 
Football and graph theory
Football and graph theoryFootball and graph theory
Football and graph theory
Umang Aggarwal
 
graph theory
graph theory graph theory
graph theory
ganith2k13
 
Interesting applications of graph theory
Interesting applications of graph theoryInteresting applications of graph theory
Interesting applications of graph theory
Tech_MX
 
Critical Path Ppt
Critical Path PptCritical Path Ppt
Critical Path Ppt
Jeff Hilton
 
Chemistry - Chp 1 - Introduction To Chemistry - PowerPoint
Chemistry - Chp 1 - Introduction To Chemistry - PowerPointChemistry - Chp 1 - Introduction To Chemistry - PowerPoint
Chemistry - Chp 1 - Introduction To Chemistry - PowerPoint
Mr. Walajtys
 
Sampling
SamplingSampling

Viewers also liked (20)

Graph Theory,Graph Terminologies,Planar Graph & Graph Colouring
Graph Theory,Graph Terminologies,Planar Graph & Graph ColouringGraph Theory,Graph Terminologies,Planar Graph & Graph Colouring
Graph Theory,Graph Terminologies,Planar Graph & Graph Colouring
 
Algorithms for Graph Coloring Problem
Algorithms for Graph Coloring ProblemAlgorithms for Graph Coloring Problem
Algorithms for Graph Coloring Problem
 
Graph T
Graph TGraph T
Graph T
 
Marketing analytics alpesh doshi social network analysis - using social gra...
Marketing analytics alpesh doshi   social network analysis - using social gra...Marketing analytics alpesh doshi   social network analysis - using social gra...
Marketing analytics alpesh doshi social network analysis - using social gra...
 
FOSDEM 2014: Social Network Benchmark (SNB) Graph Generator
FOSDEM 2014:  Social Network Benchmark (SNB) Graph GeneratorFOSDEM 2014:  Social Network Benchmark (SNB) Graph Generator
FOSDEM 2014: Social Network Benchmark (SNB) Graph Generator
 
Overview of research in chemistry
Overview of research in chemistryOverview of research in chemistry
Overview of research in chemistry
 
THE APPLICATION OF CAUSE EFFECT GRAPH FOR THE COLLEGE PLACEMENT PROCESS
THE APPLICATION OF CAUSE EFFECT GRAPH FOR THE COLLEGE PLACEMENT PROCESSTHE APPLICATION OF CAUSE EFFECT GRAPH FOR THE COLLEGE PLACEMENT PROCESS
THE APPLICATION OF CAUSE EFFECT GRAPH FOR THE COLLEGE PLACEMENT PROCESS
 
Graph theory Application
Graph theory ApplicationGraph theory Application
Graph theory Application
 
Spherule Diagrams with Graph for Social Network Visualization
Spherule Diagrams with Graph for Social Network VisualizationSpherule Diagrams with Graph for Social Network Visualization
Spherule Diagrams with Graph for Social Network Visualization
 
burton_discrete_graph theory
burton_discrete_graph theoryburton_discrete_graph theory
burton_discrete_graph theory
 
Multi-perspective Visualisation Approach for E-discovery Email Investigation
Multi-perspective Visualisation Approach for E-discovery Email InvestigationMulti-perspective Visualisation Approach for E-discovery Email Investigation
Multi-perspective Visualisation Approach for E-discovery Email Investigation
 
Data Mining Seminar - Graph Mining and Social Network Analysis
Data Mining Seminar - Graph Mining and Social Network AnalysisData Mining Seminar - Graph Mining and Social Network Analysis
Data Mining Seminar - Graph Mining and Social Network Analysis
 
Graphs - CH10 - Discrete Mathematics
Graphs - CH10 - Discrete MathematicsGraphs - CH10 - Discrete Mathematics
Graphs - CH10 - Discrete Mathematics
 
Application of graph theory in drug design
Application of graph theory in drug designApplication of graph theory in drug design
Application of graph theory in drug design
 
Football and graph theory
Football and graph theoryFootball and graph theory
Football and graph theory
 
graph theory
graph theory graph theory
graph theory
 
Interesting applications of graph theory
Interesting applications of graph theoryInteresting applications of graph theory
Interesting applications of graph theory
 
Critical Path Ppt
Critical Path PptCritical Path Ppt
Critical Path Ppt
 
Chemistry - Chp 1 - Introduction To Chemistry - PowerPoint
Chemistry - Chp 1 - Introduction To Chemistry - PowerPointChemistry - Chp 1 - Introduction To Chemistry - PowerPoint
Chemistry - Chp 1 - Introduction To Chemistry - PowerPoint
 
Sampling
SamplingSampling
Sampling
 

Similar to Coloring graphs

coloring_Graph.ppt
coloring_Graph.pptcoloring_Graph.ppt
coloring_Graph.ppt
AggarwalShailja
 
coloring.pptx
coloring.pptxcoloring.pptx
coloring.pptx
BhanuCharan9
 
coloring.ppt
coloring.pptcoloring.ppt
coloring.ppt
BhanuCharan9
 
Graph coloring with back tracking aoa.ppt
Graph coloring with back tracking aoa.pptGraph coloring with back tracking aoa.ppt
Graph coloring with back tracking aoa.ppt
ssuseraf60311
 
Exploring Concepts of Perimeter and Area.pptx
Exploring Concepts of Perimeter and Area.pptxExploring Concepts of Perimeter and Area.pptx
Exploring Concepts of Perimeter and Area.pptx
MyrrhBalanayFlorida
 
Instrumentation in Mathematics
Instrumentation in MathematicsInstrumentation in Mathematics
Instrumentation in Mathematics
Fate Jacaban
 
Instructional Materials in Mathematics
Instructional Materials in MathematicsInstructional Materials in Mathematics
Instructional Materials in Mathematics
Blenda Sotto
 
Instructional Materials in Mathematics
Instructional Materials in MathematicsInstructional Materials in Mathematics
Instructional Materials in Mathematics
Mary Caryl Yaun
 
Math chart model lesson
Math chart model lessonMath chart model lesson
Math chart model lesson
jkrutowskis
 
Infinite series
Infinite seriesInfinite series
Infinite series
ArtiSaxena10
 
SFC
SFCSFC
Geometry
GeometryGeometry
Geometry
Sushil Sharma
 
G6 m5-c-lesson 12-t
G6 m5-c-lesson 12-tG6 m5-c-lesson 12-t
G6 m5-c-lesson 12-t
mlabuski
 
Geometry Perimeter And Area 1
Geometry Perimeter And Area 1Geometry Perimeter And Area 1
Geometry Perimeter And Area 1
PJHS
 
G6 m3-c-lesson 19-t
G6 m3-c-lesson 19-tG6 m3-c-lesson 19-t
G6 m3-c-lesson 19-t
mlabuski
 
Maths
MathsMaths
Secondary Maths with Geo-boards - an overview for teachers
Secondary Maths with Geo-boards - an overview for teachersSecondary Maths with Geo-boards - an overview for teachers
Secondary Maths with Geo-boards - an overview for teachers
Jon Molomby
 
Module 4 Lesson 6
Module 4 Lesson 6Module 4 Lesson 6
Module 4 Lesson 6
NRWEG3
 
Area of Polygons_Composite Figures_.pptx
Area of Polygons_Composite Figures_.pptxArea of Polygons_Composite Figures_.pptx
Area of Polygons_Composite Figures_.pptx
LuisSalenga1
 
principles of design
principles of designprinciples of design
principles of design
DOROTHYGABAY1
 

Similar to Coloring graphs (20)

coloring_Graph.ppt
coloring_Graph.pptcoloring_Graph.ppt
coloring_Graph.ppt
 
coloring.pptx
coloring.pptxcoloring.pptx
coloring.pptx
 
coloring.ppt
coloring.pptcoloring.ppt
coloring.ppt
 
Graph coloring with back tracking aoa.ppt
Graph coloring with back tracking aoa.pptGraph coloring with back tracking aoa.ppt
Graph coloring with back tracking aoa.ppt
 
Exploring Concepts of Perimeter and Area.pptx
Exploring Concepts of Perimeter and Area.pptxExploring Concepts of Perimeter and Area.pptx
Exploring Concepts of Perimeter and Area.pptx
 
Instrumentation in Mathematics
Instrumentation in MathematicsInstrumentation in Mathematics
Instrumentation in Mathematics
 
Instructional Materials in Mathematics
Instructional Materials in MathematicsInstructional Materials in Mathematics
Instructional Materials in Mathematics
 
Instructional Materials in Mathematics
Instructional Materials in MathematicsInstructional Materials in Mathematics
Instructional Materials in Mathematics
 
Math chart model lesson
Math chart model lessonMath chart model lesson
Math chart model lesson
 
Infinite series
Infinite seriesInfinite series
Infinite series
 
SFC
SFCSFC
SFC
 
Geometry
GeometryGeometry
Geometry
 
G6 m5-c-lesson 12-t
G6 m5-c-lesson 12-tG6 m5-c-lesson 12-t
G6 m5-c-lesson 12-t
 
Geometry Perimeter And Area 1
Geometry Perimeter And Area 1Geometry Perimeter And Area 1
Geometry Perimeter And Area 1
 
G6 m3-c-lesson 19-t
G6 m3-c-lesson 19-tG6 m3-c-lesson 19-t
G6 m3-c-lesson 19-t
 
Maths
MathsMaths
Maths
 
Secondary Maths with Geo-boards - an overview for teachers
Secondary Maths with Geo-boards - an overview for teachersSecondary Maths with Geo-boards - an overview for teachers
Secondary Maths with Geo-boards - an overview for teachers
 
Module 4 Lesson 6
Module 4 Lesson 6Module 4 Lesson 6
Module 4 Lesson 6
 
Area of Polygons_Composite Figures_.pptx
Area of Polygons_Composite Figures_.pptxArea of Polygons_Composite Figures_.pptx
Area of Polygons_Composite Figures_.pptx
 
principles of design
principles of designprinciples of design
principles of design
 

More from Vikas Sharma

Divide and conquer
Divide and conquerDivide and conquer
Divide and conquer
Vikas Sharma
 
Cpp tutorial
Cpp tutorialCpp tutorial
Cpp tutorial
Vikas Sharma
 
Backtracking
BacktrackingBacktracking
Backtracking
Vikas Sharma
 
Knapsack problem
Knapsack problemKnapsack problem
Knapsack problem
Vikas Sharma
 
Rules and steps for developing a software product (rsfsp) by vikas sharma
Rules and steps for developing a software product (rsfsp) by vikas sharmaRules and steps for developing a software product (rsfsp) by vikas sharma
Rules and steps for developing a software product (rsfsp) by vikas sharma
Vikas Sharma
 
Office automation system for scholl (oasfs) by vikas sharma
Office automation system for scholl (oasfs) by vikas sharmaOffice automation system for scholl (oasfs) by vikas sharma
Office automation system for scholl (oasfs) by vikas sharma
Vikas Sharma
 
Library and member management system (lamms) by vikas sharma
Library and member management system (lamms) by vikas sharmaLibrary and member management system (lamms) by vikas sharma
Library and member management system (lamms) by vikas sharma
Vikas Sharma
 
Website optimization by vikas sharma
Website optimization by vikas sharmaWebsite optimization by vikas sharma
Website optimization by vikas sharma
Vikas Sharma
 

More from Vikas Sharma (8)

Divide and conquer
Divide and conquerDivide and conquer
Divide and conquer
 
Cpp tutorial
Cpp tutorialCpp tutorial
Cpp tutorial
 
Backtracking
BacktrackingBacktracking
Backtracking
 
Knapsack problem
Knapsack problemKnapsack problem
Knapsack problem
 
Rules and steps for developing a software product (rsfsp) by vikas sharma
Rules and steps for developing a software product (rsfsp) by vikas sharmaRules and steps for developing a software product (rsfsp) by vikas sharma
Rules and steps for developing a software product (rsfsp) by vikas sharma
 
Office automation system for scholl (oasfs) by vikas sharma
Office automation system for scholl (oasfs) by vikas sharmaOffice automation system for scholl (oasfs) by vikas sharma
Office automation system for scholl (oasfs) by vikas sharma
 
Library and member management system (lamms) by vikas sharma
Library and member management system (lamms) by vikas sharmaLibrary and member management system (lamms) by vikas sharma
Library and member management system (lamms) by vikas sharma
 
Website optimization by vikas sharma
Website optimization by vikas sharmaWebsite optimization by vikas sharma
Website optimization by vikas sharma
 

Recently uploaded

Library news letter Kitengesa Uganda June 2024
Library news letter Kitengesa Uganda June 2024Library news letter Kitengesa Uganda June 2024
Library news letter Kitengesa Uganda June 2024
Friends of African Village Libraries
 
IoT (Internet of Things) introduction Notes.pdf
IoT (Internet of Things) introduction Notes.pdfIoT (Internet of Things) introduction Notes.pdf
IoT (Internet of Things) introduction Notes.pdf
roshanranjit222
 
BỘ BÀI TẬP TEST THEO UNIT - FORM 2025 - TIẾNG ANH 12 GLOBAL SUCCESS - KÌ 1 (B...
BỘ BÀI TẬP TEST THEO UNIT - FORM 2025 - TIẾNG ANH 12 GLOBAL SUCCESS - KÌ 1 (B...BỘ BÀI TẬP TEST THEO UNIT - FORM 2025 - TIẾNG ANH 12 GLOBAL SUCCESS - KÌ 1 (B...
BỘ BÀI TẬP TEST THEO UNIT - FORM 2025 - TIẾNG ANH 12 GLOBAL SUCCESS - KÌ 1 (B...
Nguyen Thanh Tu Collection
 
Information and Communication Technology in Education
Information and Communication Technology in EducationInformation and Communication Technology in Education
Information and Communication Technology in Education
MJDuyan
 
A Quiz on Drug Abuse Awareness by Quizzito
A Quiz on Drug Abuse Awareness by QuizzitoA Quiz on Drug Abuse Awareness by Quizzito
A Quiz on Drug Abuse Awareness by Quizzito
Quizzito The Quiz Society of Gargi College
 
Contiguity Of Various Message Forms - Rupam Chandra.pptx
Contiguity Of Various Message Forms - Rupam Chandra.pptxContiguity Of Various Message Forms - Rupam Chandra.pptx
Contiguity Of Various Message Forms - Rupam Chandra.pptx
Kalna College
 
220711130095 Tanu Pandey message currency, communication speed & control EPC ...
220711130095 Tanu Pandey message currency, communication speed & control EPC ...220711130095 Tanu Pandey message currency, communication speed & control EPC ...
220711130095 Tanu Pandey message currency, communication speed & control EPC ...
Kalna College
 
How to stay relevant as a cyber professional: Skills, trends and career paths...
How to stay relevant as a cyber professional: Skills, trends and career paths...How to stay relevant as a cyber professional: Skills, trends and career paths...
How to stay relevant as a cyber professional: Skills, trends and career paths...
Infosec
 
220711130088 Sumi Basak Virtual University EPC 3.pptx
220711130088 Sumi Basak Virtual University EPC 3.pptx220711130088 Sumi Basak Virtual University EPC 3.pptx
220711130088 Sumi Basak Virtual University EPC 3.pptx
Kalna College
 
Non-Verbal Communication for Tech Professionals
Non-Verbal Communication for Tech ProfessionalsNon-Verbal Communication for Tech Professionals
Non-Verbal Communication for Tech Professionals
MattVassar1
 
Accounting for Restricted Grants When and How To Record Properly
Accounting for Restricted Grants  When and How To Record ProperlyAccounting for Restricted Grants  When and How To Record Properly
Accounting for Restricted Grants When and How To Record Properly
TechSoup
 
Slides Peluncuran Amalan Pemakanan Sihat.pptx
Slides Peluncuran Amalan Pemakanan Sihat.pptxSlides Peluncuran Amalan Pemakanan Sihat.pptx
Slides Peluncuran Amalan Pemakanan Sihat.pptx
shabeluno
 
Brand Guideline of Bashundhara A4 Paper - 2024
Brand Guideline of Bashundhara A4 Paper - 2024Brand Guideline of Bashundhara A4 Paper - 2024
Brand Guideline of Bashundhara A4 Paper - 2024
khabri85
 
pol sci Election and Representation Class 11 Notes.pdf
pol sci Election and Representation Class 11 Notes.pdfpol sci Election and Representation Class 11 Notes.pdf
pol sci Election and Representation Class 11 Notes.pdf
BiplabHalder13
 
Interprofessional Education Platform Introduction.pdf
Interprofessional Education Platform Introduction.pdfInterprofessional Education Platform Introduction.pdf
Interprofessional Education Platform Introduction.pdf
Ben Aldrich
 
The Rise of the Digital Telecommunication Marketplace.pptx
The Rise of the Digital Telecommunication Marketplace.pptxThe Rise of the Digital Telecommunication Marketplace.pptx
The Rise of the Digital Telecommunication Marketplace.pptx
PriyaKumari928991
 
Observational Learning
Observational Learning Observational Learning
Observational Learning
sanamushtaq922
 
Ethiopia and Eritrea Eritrea's journey has been marked by resilience and dete...
Ethiopia and Eritrea Eritrea's journey has been marked by resilience and dete...Ethiopia and Eritrea Eritrea's journey has been marked by resilience and dete...
Ethiopia and Eritrea Eritrea's journey has been marked by resilience and dete...
biruktesfaye27
 
220711130100 udita Chakraborty Aims and objectives of national policy on inf...
220711130100 udita Chakraborty  Aims and objectives of national policy on inf...220711130100 udita Chakraborty  Aims and objectives of national policy on inf...
220711130100 udita Chakraborty Aims and objectives of national policy on inf...
Kalna College
 
managing Behaviour in early childhood education.pptx
managing Behaviour in early childhood education.pptxmanaging Behaviour in early childhood education.pptx
managing Behaviour in early childhood education.pptx
nabaegha
 

Recently uploaded (20)

Library news letter Kitengesa Uganda June 2024
Library news letter Kitengesa Uganda June 2024Library news letter Kitengesa Uganda June 2024
Library news letter Kitengesa Uganda June 2024
 
IoT (Internet of Things) introduction Notes.pdf
IoT (Internet of Things) introduction Notes.pdfIoT (Internet of Things) introduction Notes.pdf
IoT (Internet of Things) introduction Notes.pdf
 
BỘ BÀI TẬP TEST THEO UNIT - FORM 2025 - TIẾNG ANH 12 GLOBAL SUCCESS - KÌ 1 (B...
BỘ BÀI TẬP TEST THEO UNIT - FORM 2025 - TIẾNG ANH 12 GLOBAL SUCCESS - KÌ 1 (B...BỘ BÀI TẬP TEST THEO UNIT - FORM 2025 - TIẾNG ANH 12 GLOBAL SUCCESS - KÌ 1 (B...
BỘ BÀI TẬP TEST THEO UNIT - FORM 2025 - TIẾNG ANH 12 GLOBAL SUCCESS - KÌ 1 (B...
 
Information and Communication Technology in Education
Information and Communication Technology in EducationInformation and Communication Technology in Education
Information and Communication Technology in Education
 
A Quiz on Drug Abuse Awareness by Quizzito
A Quiz on Drug Abuse Awareness by QuizzitoA Quiz on Drug Abuse Awareness by Quizzito
A Quiz on Drug Abuse Awareness by Quizzito
 
Contiguity Of Various Message Forms - Rupam Chandra.pptx
Contiguity Of Various Message Forms - Rupam Chandra.pptxContiguity Of Various Message Forms - Rupam Chandra.pptx
Contiguity Of Various Message Forms - Rupam Chandra.pptx
 
220711130095 Tanu Pandey message currency, communication speed & control EPC ...
220711130095 Tanu Pandey message currency, communication speed & control EPC ...220711130095 Tanu Pandey message currency, communication speed & control EPC ...
220711130095 Tanu Pandey message currency, communication speed & control EPC ...
 
How to stay relevant as a cyber professional: Skills, trends and career paths...
How to stay relevant as a cyber professional: Skills, trends and career paths...How to stay relevant as a cyber professional: Skills, trends and career paths...
How to stay relevant as a cyber professional: Skills, trends and career paths...
 
220711130088 Sumi Basak Virtual University EPC 3.pptx
220711130088 Sumi Basak Virtual University EPC 3.pptx220711130088 Sumi Basak Virtual University EPC 3.pptx
220711130088 Sumi Basak Virtual University EPC 3.pptx
 
Non-Verbal Communication for Tech Professionals
Non-Verbal Communication for Tech ProfessionalsNon-Verbal Communication for Tech Professionals
Non-Verbal Communication for Tech Professionals
 
Accounting for Restricted Grants When and How To Record Properly
Accounting for Restricted Grants  When and How To Record ProperlyAccounting for Restricted Grants  When and How To Record Properly
Accounting for Restricted Grants When and How To Record Properly
 
Slides Peluncuran Amalan Pemakanan Sihat.pptx
Slides Peluncuran Amalan Pemakanan Sihat.pptxSlides Peluncuran Amalan Pemakanan Sihat.pptx
Slides Peluncuran Amalan Pemakanan Sihat.pptx
 
Brand Guideline of Bashundhara A4 Paper - 2024
Brand Guideline of Bashundhara A4 Paper - 2024Brand Guideline of Bashundhara A4 Paper - 2024
Brand Guideline of Bashundhara A4 Paper - 2024
 
pol sci Election and Representation Class 11 Notes.pdf
pol sci Election and Representation Class 11 Notes.pdfpol sci Election and Representation Class 11 Notes.pdf
pol sci Election and Representation Class 11 Notes.pdf
 
Interprofessional Education Platform Introduction.pdf
Interprofessional Education Platform Introduction.pdfInterprofessional Education Platform Introduction.pdf
Interprofessional Education Platform Introduction.pdf
 
The Rise of the Digital Telecommunication Marketplace.pptx
The Rise of the Digital Telecommunication Marketplace.pptxThe Rise of the Digital Telecommunication Marketplace.pptx
The Rise of the Digital Telecommunication Marketplace.pptx
 
Observational Learning
Observational Learning Observational Learning
Observational Learning
 
Ethiopia and Eritrea Eritrea's journey has been marked by resilience and dete...
Ethiopia and Eritrea Eritrea's journey has been marked by resilience and dete...Ethiopia and Eritrea Eritrea's journey has been marked by resilience and dete...
Ethiopia and Eritrea Eritrea's journey has been marked by resilience and dete...
 
220711130100 udita Chakraborty Aims and objectives of national policy on inf...
220711130100 udita Chakraborty  Aims and objectives of national policy on inf...220711130100 udita Chakraborty  Aims and objectives of national policy on inf...
220711130100 udita Chakraborty Aims and objectives of national policy on inf...
 
managing Behaviour in early childhood education.pptx
managing Behaviour in early childhood education.pptxmanaging Behaviour in early childhood education.pptx
managing Behaviour in early childhood education.pptx
 

Coloring graphs

  • 1. Coloring Graphs This handout: • Coloring maps and graphs • Chromatic number • Applications of graph coloring
  • 2. Coloring maps • Color a map such that two regions with a common border are assigned different colors. • Each map can be represented by a graph: – Each region of the map is represented by a vertex; – Edges connect two vertices if the regions represented by these vertices have a common border. • The resulting graph is called the dual graph of the map.
  • 3. Coloring Graphs • Definition: A graph has been colored if a color has been assigned to each vertex in such a way that adjacent vertices have different colors. • Definition: The chromatic number of a graph is the smallest number of colors with which it can be colored. In the example above, the chromatic number is 4.
  • 4. Coloring Planar Graphs • Definition: A graph is planar if it can be drawn in a plane without edge-crossings. • The four color theorem: For every planar graph, the chromatic number is ≤ 4. Was posed as a conjecture in the 1850s. Finally proved in 1976 (Appel and Haken) by the aid of computers.
  • 5. An application of graph coloring in scheduling Twelve faculty members in a mathematics department serve on the following committees:  Undergraduate education: Sineman, Limitson, Axiomus, Functionini  Graduate Education: Graphian, Vectorades, Functionini, Infinitescu  Colloquium: Lemmeau, Randomov, Proofizaki  Library: Van Sum, Sineman, Lemmeau  Staffing: Graphian, Randomov, Vectorades, Limitson  Promotion: Vectorades, Van Sum, Parabolton The committees must all meet during the first week of classes, but there are only three time slots available. Find a schedule that will allow all faculty members to attend the meetings of all committees on which they serve.
  • 6. An application of graph coloring in exam scheduling Suppose that in a particular quarter there are students taking each of the following combinations of courses:  Math, English, Biology, Chemistry  Math, English, Computer Science, Geography  Biology, Psychology, Geography, Spanish  Biology, Computer Science, History, French  English, Psychology, Computer Science, History  Psychology, Chemistry, Computer Science, French  Psychology, Geography, History, Spanish What is the minimum number of examination periods required for the exams in the ten courses specified so that students taking any of the given combinations of courses have no conflicts? Find a schedule that uses this minimum number of periods.
  • 7. An application of graph coloring in exam scheduling Suppose that in a particular quarter there are students taking each of the following combinations of courses:  Math, English, Biology, Chemistry  Math, English, Computer Science, Geography  Biology, Psychology, Geography, Spanish  Biology, Computer Science, History, French  English, Psychology, Computer Science, History  Psychology, Chemistry, Computer Science, French  Psychology, Geography, History, Spanish What is the minimum number of examination periods required for the exams in the ten courses specified so that students taking any of the given combinations of courses have no conflicts? Find a schedule that uses this minimum number of periods.
  翻译: