Эксперт по сдаче вступительных испытаний в ВУЗах
Вопрос: » Для графа G(X,U), где #math U={(!(#l(x,1)$#l(x,2)))%(!(#l(x,3)$#l(x,4)))%(!(#l(x,3)$#l(x,3)))%(!(#l(x,2)$#l(x,2)))%(!(#l(x,1)$#l(x,3)))%(!(#l(x,1)$#l(x,4)))%(!(#l(x,4)$#l(x,2)))}.
Определить:
а) хроматическое число #math gamma$(G);
б) все максимальные пустые подграфы P(G) методом Магу;
в) множества вершин K(G), которым можно приписать одно и тоже натуральное число(цвет).
Варианты ответа:
1. #math gamma$(G)=3;
#math P$(G)={#l(x,1)%#l(x,4)%#l(x,2)$#l(x,3)};
#math K$(G)={#l(x,1)%#l(x,4)%#l(x,2)$#l(x,3)}.
2. #math gamma$(G)=3;
#math P$(G)={#l(x,1)%#l(x,3)%#l(x,2)$#l(x,4)};
#math K$(G)={#l(x,1)%#l(x,3)%#l(x,2)$#l(x,4)}.
3. #math gamma$(G)=2;
#math P$(G)={#l(x,1)$#l(x,3)%#l(x,2)$#l(x,3)};
#math K$(G)={#l(x,2)%#l(x,4)%#l(x,1)$#l(x,3)}.
В ответ введите номер верного варианта ответа. »
Ответ (1)
Вопрос: » Для графа G(X,U), где #math U={(!(#l(x,1)$#l(x,2)))%(!(#l(x,3)$#l(x,4)))%(!(#l(x,3)$#l(x,3)))%(!(#l(x,3)$#l(x,2)))%(!(#l(x,1)$#l(x,3)))%(!(#l(x,1)$#l(x,4)))%(!(#l(x,4)$#l(x,4)))}.
Определить:
а) хроматическое число #math gamma$(G);
б) все максимальные пустые подграфы P(G) методом Магу;
в) множества вершин K(G), которым можно приписать одно и тоже натуральное число(цвет).
Варианты ответа:
1. #math gamma$(G)=3;
#math P$(G)={#l(x,2)$#l(x,3)%#l(x,1)%#l(x,2)$#l(x,4)};
#math K$(G)={#l(x,2)%#l(x,4)%#l(x,2)$#l(x,4)}.
2. #math gamma$(G)=3;
#math P$(G)={#l(x,1)%#l(x,3)%#l(x,2)$#l(x,4)};
#math K$(G)={#l(x,1)%#l(x,3)%#l(x,2)$#l(x,4)}.
3. #math gamma$(G)=2;
#math P$(G)={#l(x,1)$#l(x,3)%#l(x,2)$#l(x,3)};
#math K$(G)={#l(x,2)%#l(x,4)%#l(x,1)$#l(x,3)}.
В ответ введите номер верного варианта ответа. »
Ответ (2)
Вопрос: «Раскрасить граф G=(X,U) , применяя метод Магу, если #math U={(!(#l(x,1)$#l(x,2)))%(!(#l(x,3)$#l(x,4)))%(!(#l(x,2)$#l(x,3)))%(!(#l(x,4)$#l(x,5)))%(!(#l(x,3)$#l(x,3)))%(!(#l(x,2)$#l(x,6)))%(!(#l(x,5)$#l(x,6)))%(!(#l(x,5)$#l(x,5)))%(!(#l(x,6)$#l(x,7)))}.
Определить:
а) хроматическое число #math gamma$(G);
б) все максимальные пустые подграфы P(G) методом Магу;
в) множества вершин K(G), которым можно приписать одно и тоже натуральное число.
Варианты ответа:
1. #math gamma$(G)=3;
#math P$(G)={#l(x,1)$#l(x,3)$#l(x,6)%#l(x,1)$#l(x,4)$#l(x,6)%#l(x,1)$#l(x,4)$#l(x,7)%#l(x,2)$#l(x,4)$#l(x,7)%#l(x,2)$#l(x,5)$#l(x,7)%#l(x,1)$#l(x,3)$#l(x,5)$#l(x,7)};
#math K$(G)={#l(x,2)%#l(x,4)$#l(x,6)%#l(x,1)$#l(x,3)$#l(x,5)$#l(x,7)}%{#l(x,6)%#l(x,2)$#l(x,4)%#l(x,1)$#l(x,3)$#l(x,5)$#l(x,7)}.
2. #math gamma$(G)=3;
#math P$(G)={#l(x,2)$#l(x,3)%#l(x,1)$#l(x,3)$#l(x,7)%#l(x,1)$#l(x,5)$#l(x,6)%#l(x,1)$#l(x,4)$#l(x,7)%#l(x,2)$#l(x,3)$#l(x,7)%#l(x,2)$#l(x,5)$#l(x,7)%#l(x,1)$#l(x,3)$#l(x,5)$#l(x,7)};
#math K$(G)={#l(x,1)%#l(x,3)$#l(x,6)%#l(x,1)$#l(x,3)$#l(x,5)$#l(x,7)}%{#l(x,6)%#l(x,2)$#l(x,4)%#l(x,1)$#l(x,3)$#l(x,5)$#l(x,6)}.
3. #math gamma$(G)=2;
#math P$(G)={#l(x,1)$#l(x,3)%#l(x,1)$#l(x,3)$#l(x,6)%#l(x,1)$#l(x,4)$#l(x,6)%#l(x,1)$#l(x,4)$#l(x,7)%#l(x,3)$#l(x,4)$#l(x,7)%#l(x,2)$#l(x,5)$#l(x,7)%#l(x,2)$#l(x,3)$#l(x,5)$#l(x,7)};
#math K$(G)={#l(x,2)%#l(x,4)$#l(x,6)%#l(x,1)$#l(x,3)$#l(x,5)$#l(x,7)}%{#l(x,6)%#l(x,2)$#l(x,4)%#l(x,1)$#l(x,3)$#l(x,5)$#l(x,7)}.
В ответ введите номер верного варианта ответа. »
Ответ (1)
Вопрос: «Раскрасить граф G=(X,U) , применяя метод Магу, если
#math U={#math(!(#l(x,1)$#l(x,2)))%(!(#l(x,3)$#l(x,4)))%(!(#l(x,2)$#l(x,3)))%(!(#l(x,4)$#l(x,5)))%(!(#l(x,2)$#l(x,6)))%(!(#l(x,5)$#l(x,6)))%(!(#l(x,6)$#l(x,7)))%(!(#l(x,1)$#l(x,3)))%(!(#l(x,2)$#l(x,4)))%(!(#l(x,5)$#l(x,7)))}.
Определить:
а) хроматическое число #math gamma$(G);
б) все максимальные пустые подграфы P(G) методом Магу;
в) множества вершин K(G), которым можно приписать одно и тоже натуральное число(цвет).
Варианты ответа:
1. #math gamma$(G)=3;
#math P$(G)={#math#l(x,2)$#l(x,3)$#l(x,5)$#l(x,6)%#l(x,2)$#l(x,3)$#l(x,5)$#l(x,7)%#l(x,2)$#l(x,3)$#l(x,4)$#l(x,6)$#l(x,7)#math%#l(x,1)$#l(x,3)$#l(x,4)$#l(x,5)$#l(x,6)%#l(x,1)$#l(x,3)$#l(x,4)$#l(x,6)$#l(x,7)%#math#l(x,1)$#l(x,2)$#l(x,4)$#l(x,5)$#l(x,6)%#math$#l(x,1)$#l(x,2)$#l(x,4)$#l(x,5)$#l(x,7)%#l(x,1)$#l(x,2)$#l(x,4)$#l(x,6)$#l(x,7)};
#math K$(G)={#l(x,2)$#l(x,5)%#l(x,3)$#l(x,6)%#l(x,1)$#l(x,4)$#l(x,7)}%{#l(x,2)$#l(x,5)%#l(x,3)$#l(x,7)%#l(x,1)$#l(x,4)$#l(x,6)}.
2. #math gamma$(G)=3;
#math P$(G)={#math#l(x,1)$#l(x,2)$#l(x,5)$#l(x,6)%#l(x,2)$#l(x,3)$#l(x,6)$#l(x,7)%#l(x,2)$#l(x,3)$#l(x,4)$#l(x,6)$#l(x,7)#math%#l(x,1)$#l(x,3)$#l(x,4)$#l(x,6)%#l(x,1)$#l(x,3)$#l(x,4)$#l(x,5)$#l(x,6)%#math$#l(x,1)$#l(x,3)$#l(x,4)$#l(x,6)$#l(x,7)%#l(x,1)$#l(x,2)$#l(x,4)$#l(x,5)$#l(x,6)%#math$#l(x,1)$#l(x,2)$#l(x,4)$#l(x,5)$#l(x,7)};
#math K$(G)={#l(x,1)%#l(x,3)$#l(x,6)%#l(x,1)$#l(x,3)$#l(x,5)$#l(x,7)}%{#l(x,6)%#l(x,2)$#l(x,4)%#l(x,1)$#l(x,3)$#l(x,5)$#l(x,6)}.
3. #math gamma$(G)=2;
#math P$(G)={#math#l(x,2)$#l(x,3)$#l(x,5)$#l(x,6)%#l(x,1)$#l(x,3)$#l(x,5)$#l(x,7)%#l(x,2)$#l(x,3)$#l(x,4)$#l(x,6)$#l(x,7)#math%#l(x,1)$#l(x,3)$#l(x,4)$#l(x,6)$#l(x,7)%#l(x,2)$#l(x,3)$#l(x,4)$#l(x,5)$#l(x,6)%#math$#l(x,1)$#l(x,2)$#l(x,4)$#l(x,6)$#l(x,7)%#l(x,1)$#l(x,2)$#l(x,4)$#l(x,5)$#l(x,6)%#math$#l(x,2)$#l(x,2)$#l(x,4)$#l(x,5)$#l(x,7)};
#math K$(G)={#l(x,2)%#l(x,4)$#l(x,6)%#l(x,1)$#l(x,3)$#l(x,5)$#l(x,7)}%{#l(x,6)%#l(x,2)$#l(x,4)%#l(x,1)$#l(x,3)$#l(x,5)$#l(x,7)}.
В ответ введите номер верного варианта ответа.
Ответ (1)
Связность графа.
Вопрос: » Определить число компонент связности K(G) графа G=(X,U),
где #math U={#math(!(#l(x,1)$#l(x,2)))%(!(#l(x,3)$#l(x,4)))%(!(#l(x,2)$#l(x,3)))%(!(#l(x,4)$#l(x,5)))%(!(#l(x,2)$#l(x,6)))%#math(!(#l(x,5)$#l(x,6)))%(!(#l(x,6)$#l(x,7)))%(!(#l(x,8)$#l(x,9)))%(!(#l(x,10)$#l(x,11)))%(!(#l(x,11)$#l(x,10)))%#math(!(#l(x,10)$#l(x,9)))%(!(#l(x,9)$#l(x,10)))%(!(#l(x,8)$#l(x,10)))%(!(#l(x,8)$#l(x,11)))%(!(#l(x,9)$#l(x,11)))}. »
Ответ (2)
Вопрос: » Определить число компонент связности H(G) графа G=(X,U),
где #math U={#math(!(#l(x,1)$#l(x,2)))%(!(#l(x,3)$#l(x,4)))%(!(#l(x,2)$#l(x,3)))%(!(#l(x,4)$#l(x,5)))%(!(#l(x,2)$#l(x,6)))%#math(!(#l(x,5)$#l(x,6)))%(!(#l(x,6)$#l(x,7)))%#i((#l(x,10)$#l(x,9)),null,@arr$)%(!(#l(x,8)$#l(x,9)))%#i((#l(x,10)$#l(x,11)),null,@arr$)%#math#i((#l(x,11)$#l(x,10)),null,@arr$)%#i((#l(x,9)$#l(x,10)),null,@arr$)%(!(#l(x,8)$#l(x,10)))%(!(#l(x,8)$#l(x,11)))%(!(#l(x,9)$#l(x,11)))}
и показать, как изменятся номера вершин после отождествления вершины #math #l(x,2) с вершиной #math #l(x,5).
Варианты ответа:
1. H=2; 1-11,2-10,3-5,4-3,5-10,6-3,7-8,9-6,8-7,10-8,11-9.
2. H=2; 1-1,2-11,3-2,4-3,6-10,5-4,7-5,8-6,9-7,11-8,10-9.
3. H=2; 1-1,2-10,3-2,4-3,5-10,6-4,7-5,8-6,9-7,10-8,11-9.
В ответ введите номер верного варианта ответа. »
Ответ (3)
