3 Присутствует в d2 -множестве. В целом, распределение цветов в Di -
множествах, i = 1, 4, см. в табл. 3.3. Более того, в P R3(4) цвета вершин
Di -множеств, i = 1, 4, задаются по следующим правилам:
6
6
6
Цвета вершин v из D2-множества задаются так, что:
6
6
6
Цвета вершин x из D3-множества задаются так, что:
6
6
6
Цвета вершин y из D4-множества задаются так, что:
6
6
6
При покраске P R4(4) в три цвета учитываются цвета r4 -смежных вер- шин в P Ri (4), i = 1, 3, i = 5. (Распределение цветов в Di -множествах, i = 1, 4 в P R4(4) см. в табл. 3.3). Правила покраски определяются следу- ющим образом. Цвета вершин v из D1-множества определяются как:
6
6
6
Цвета вершин v из D2 -множества задаются так, что:
6
6
6
Цвета вершин x из D3-множества задаются так, что:
6
6
6
Цвета вершин y из D4-множества задаются так, что:
6
6
6
Таким образом, в S5(P R) задана 3-раскраска, при которой каждый из P Ri (4), i = 1, 5, имеет правильную 3-раскраску, все r4-смежные верши- ны имеют правильную 3-раскраску, и следовательно, 3-раскраска S5 (P R) является правильной.
Таблица 3.2. Раскраска доминирующих множеств в S5(P R) в четыре цвета
-
P R1 (4)
P R2 (4)
P R3 (4)
P R4 (4)
P R5 (4)
D1
c1
c4
c2
c2
c4
D2
c2
c2
c3
c4
c2
D3
c3
c3
c4
c3
c3
D4
c4
c1
c1
c1
c1
Таблица 3.3. Распределение цветов в доминирующих множествах после покраски S5(P R) в три цвета
-
1
1
2
3
1
2
3
1
2
3
2
2
3
1
2
3
1
2
3
1
2
1
3
2
3
1
2
3
1
2
3
1
2
3
1
3
P
R1(4)
P
R2(4)
P
R3
(4)
P
R4(4)
P
R5
(4)
D1
c6
c3
−
c2
−
c1
c1
−
c4
−
c1
c1
−
c4
−
c1
c6
D2
c3
−
c3
c3
−
c1
−
c2
c2
−
c2
−
c2
c4
−
c2
c3
−
c3
D3
c3
−
c3
c2
−
c2
−
c2
c3
−
c1
−
c2
c1
−
c2
−
c3
c3
−
c3
D4
c3 3
3
3
3
2
1
2
1
3
3
3
Приведем пример 3-раскраски S5(P R). Положим c1 = 1, c2 = 2, c3 = 3
и на рис. 3.5 и 3.6 покажем 4- и 3-раскраску.
1
13
✈✟✟✈❍❍✈
8
21
✟❍✈
17
❍✈10
7 ❍✈✟✟✈14
2
9 ❍✟✈
22
✟✈18
15
19
✈✟✟✈❍❍✈
4
11
✟❍✈
23
❍✈6
3 ❍✈❍
✟✈20
5 ❍ ✟✈24
1
39
✟❍✈
35
16
❍✈28
P R1(4)
12 26
49 ✟✈✟❍✈❍✈44
24
53 ✈✟✟✈❍❍✈46
25 ❍✈✟✟✈32
5
27 ❍✟✈
40
✟✈36
43 ✈❍❍✟✈✟✈50
30
45 ❍✈✟✟✈54
19
33
37 ✈✟✟✈❍❍✈ 6
29
✟❍✈
41
❍✈4
51
22 ✟✈✟❍✈❍✈29
47
20 ✈✟✟✈❍❍✈28
3 ❍✈✟✟✈38
2 ❍ ✟✈42
27 ✈❍❍✟✈✟✈23
25 ❍✈✟✟✈21
34 P R5(4) 30
39 56
52 P R2(4) 48
31 50
43
✈✟✟❍✈❍✈10
48 ✟❍✈❍✈8
16 ✟❍✈❍✈56
14 ✈✟✟❍✈❍✈58
7 ❍✟✈✟✈46
38
12 ✈❍❍✟✈✟✈44
60
55 ✈❍❍✟✈✟✈17
36
57 ❍✈✟
51
✟✈15
45
58 ✟✈✟❍✈❍✈37
11
59 ✟❍✈❍✈41
18
✟❍✈
54
❍✈35
59
52 ✈✟✟✈❍
❍✈33
42 ❍✟✈✟✈55
40 ✈❍❍✟✈✟✈57
34 ✈❍❍
✟✈49
32 ❍✈✟✟✈53
47 P R4(4) 9
13 P R3 (4) 60
Рис. 3.5. 4-раскраска S5(P R)
(вершины имеющие одинаковые номера являются r4 -смежными)
1
13 ✈✟✟✈❍❍✈ 8
21
✟❍✈
17
❍✈10
7 ❍✈✟✟✈14
2
9 ❍✟✈
22
✟✈18
15
19 ✈✟✟✈❍❍✈ 4
11
✟❍✈
23
❍✈6
3 ❍✈❍
✟✈20
5 ❍ ✟✈24
1
31 ✈✟✟✈❍❍✈26
39
✟❍✈
35
16
❍✈28
P R1(4)
12 26
49 ✟✈✟❍✈❍✈44
24
53 ✈✟✟✈❍❍✈46
25 ❍✈✟✟✈32
5
27 ❍✟✈
40
✟✈36
43 ✈❍❍✟✈✟✈50
30
45 ❍✈✟✟✈54
19
33
37 ✈✟✟✈❍❍✈ 6
29
41
❍✈4
51
22 ✟✈✟❍✈❍✈29
47
20 ✈✟✟✈❍❍✈28
3 ❍✈✟✟✈38
2 ❍ ✟✈42
27 ✈❍❍✟✈✟✈23
25 ❍✈✟✟✈21
34 P R5(4) 30
39 56
52 P R2(4) 48
31 50
43 ✈✟✟❍✈❍✈10
48 ✟❍✈❍✈8
16 ✟❍✈❍✈56
14 ✈✟✟❍✈❍✈58
7 ❍✟✈✟✈46
38
12 ✈❍❍✟✈✟✈44
60
55 ✈❍❍✟✈✟✈17
36
57 ❍✈✟
51
✟✈15
45
58 ✟✈✟❍✈❍✈37
11
59 ✟❍✈❍✈41
18
✟❍✈
54
❍✈35
59
52 ✈✟✟✈❍
❍✈33
42 ❍✟✈✟✈55
40 ✈❍❍✟✈✟✈57
34 ✈❍❍
✟✈49
32 ❍✈✟✟✈53
47 P R4(4) 9
13 P R3 (4) 60
Рис. 3.6. 3-раскраска S5 (P R)
(вершины, имеющие одинаковые номера, связаны r4 -ребром)
Список литературы
[1] Ф.Харари. Теория графов. М.: Мир, 1973. 300 c.
[2] R.L.Brooks. On colouring the nodes of a network, Proc. Cambridge Phil.
Soc., 37 (1941) 194–197.
[3] H. Dweighter, E 2569 in: Elementary problems and solutions, Amer. Math.
Monthly , 82 (1) (1975) 1010.
[4] E. Konstantinova. Combinatorial problems on Caley graphs, in: Lectures on Combinatorics 1. IPM Lecture Notes Series 8, pp. 67–140.
[5] L. Heydemann. Caley graphs as interconnection networks, in: Graph symmetry: algebraic methods and applications, (G. Halun, G. Sabidussi, eds.), Kluwer, Amsterdam, 1997.
[6] M. Heydari and Sudborough. On Sorting by prefix reversals and the diameter of pancake networks, Lecture notes in computer Science, 678 (1992) 218–227.