Chart Coloring .


25 views
Uploaded on:
Description
Definition. A shading of a straightforward diagram is the task of a shading to every vertex of the chart so that no two adjoining vertices are allocated the same shading. . . . . . . . . . . . Chromatic Number. The chromatic number of a chart is minimal number of hues required to do a shading of a diagram .
Transcripts
Slide 1

Chart Coloring March 25, 2004 CS 146 (1:30 pm-2:45 pm) by Park, Jong Seok

Slide 2

Definition A shading of a straightforward diagram is the task of a shading to every vertex of the chart so that no two contiguous vertices are doled out a similar shading.

Slide 3

Chromatic Number The chromatic number of a chart is minimal number of hues required to do a shading of a diagram

Slide 4

What is the chromatic number of this diagram?

Slide 5

Algorithm Assign shading 1 to the vertex with most noteworthy degree. Likewise dole out shading 1 to any vertex that is not associated with this vertex. Allocate shading 2 to the vertex with the following most noteworthy degree that is not officially hued. Additionally dole out shading 2 to any vertex not associated with this vertex and that is not effectively hued. On the off chance that uncolored vertices remain, dole out shading 3 to the uncolored vertex with next most astounding degree and other uncolored, detached vertices. Continue in this way until all vertices are shaded.

Slide 6

Practice

Slide 7

Application e.g. Booking Final Exams Suppose you need to timetable end of the year tests and, being extremely thoughtful, you need to abstain from having an understudy accomplish more than one exam a day. We might call the courses 1,2,3,4,5,6,7. In the table underneath a star in section ij implies that course i and j have no less than one understudy in like manner so you can\'t have them around the same time. What is minimal number of days you have to calendar every one of the exams? Demonstrate how you would plan the exams.

Slide 9

2 1 3 4 5 4 5 6 7

Slide 10

1 2 6 2 6 7 3 5 3 5 4

Slide 11

1 2 3 4

Recommended
View more...