Рубрики

ВОРОТА | GATE IT 2006 | Вопрос 25

Рассмотрим неориентированный граф G, определенный следующим образом. Вершинами G являются битовые строки длины n. У нас есть грань между вершиной u и вершиной v в том и только в том случае, если u и v различаются ровно на одну позицию бита (другими словами, v можно получить из u, щелкнув один бит). Отношение хроматического числа G к диаметру G составляет
(А) 1 / (2 на )
(B) 1 / n
(С) 2 / n
(D) 3 / n

Ответ: (с)
Пояснение: <! — Данный граф является определением графа гиперкуба
хроматическое число для этого = 2
диаметр = н
Итак, отношение = 2 / н
->

Двудольный граф: — Двудольный граф — это граф G (V, E), в котором вершины могут быть разложены на два непересекающихся множества так, что никакие две вершины в одном и том же наборе не являются смежными.

Диаметр графа: — Самый длинный кратчайший путь между любыми двумя вершинами графа. Данный граф является двудольным графом => хроматическое число равно 2 Диаметр графа равен n, потому что самое большее нам нужно пройти n- 1 ребра.

Рекомендуемые посты:

ВОРОТА | GATE IT 2006 | Вопрос 25

0.00 (0%) 0 votes