ВОРОТА | ВОРОТА КС 2021 | Набор 1 | Вопрос 46

Пусть G=(V,E) — неориентированный невзвешенный связный граф. Диаметр G определяется как:

Пусть M будет матрицей смежности G.

Определим граф G2 на том же множестве вершин с матрицей смежности N, где

Какое из следующих утверждений верно?
(A) диам(G ₂ )≤⌈ диам(G)/2⌉
(B) ⌈ диам.(G)/2⌉ 2 )< диам.(G)
(C) диам(G ₂ ) = диам(G)
(D) диаметр(G)< диаметр(G2)≤2 диаметр( _G )

Ответ: (А)
Объяснение: M ² будет матрицей смежности графа H, полученной из G следующим образом:

H(a,b) = 1 iff (there exists a vertex c st. G(a,c) = 1 and G(c,b) = 1)

Таким образом, в основном существует ребро между a, b тогда и только тогда, когда существует некоторая вершина c st. в G есть ребро (a,c) и ребро (c,b).
Когда мы делаем G∪H, в результирующем графе диаметр уменьшается до 0,5 исходного графа.

Альтернатива:

Данный граф G всегда будет связным графом (как уже упоминалось).

Поскольку граф является невзвешенным графом, кратчайший путь между вершинами - это минимальное количество ребер, через которые нужно пройти. Дана M — матрица смежности графа G, а N — матрица смежности графа G2. Ячейки в матрице N удовлетворяют условию, состоящему в том, что она имеет значение 1, если M _ij > 0 или M ² _ij > 0 и 0 в противном случае.

В качестве базового случая для графа G для двух или трех вершин диаметр (G) будет равен 1, поскольку кратчайший путь находится на расстоянии 1 единицы от каждой вершины. После этого граф G2 должен быть сформирован из тех вершин, которые находятся на соответствующих позициях. Граф G2 такой же, как G. Следовательно, diam(G) = diam(G2) { для | В | = {2,3} }

для | В | in { 3, 6 } Как показано, квадрат матрицы M ( P ) в сочетании с M обеспечивает дополнительные ребра между вершинами, которые находятся на расстоянии 2 единиц друг от друга.

На первом рисунке для | В | = 4, diam(G) = 2 (вершины A и C находятся на расстоянии 2 единиц друг от друга) после возведения в квадрат матрицы смежности M мы получаем дополнительные ячейки, получающие 1 в матрице N, которая включает ребра между этими двумя вершинами, которые находятся на расстоянии двух единиц от друг друга, т.е. ребра AC и BD. Таким образом, diam(G2) = 1. Поскольку все вершины можно посетить не более чем за 1 единицу.

Аналогично для графика | В | = 6, diam(G) = 3 (вершины B и E находятся на расстоянии 3 единиц друг от друга) после возведения в квадрат матрицы 6 X 6 мы получаем P( M ² ), который включает дополнительные ребра BD, DF, FB, CE, EA, переменного тока. Таким образом, все вершины можно посетить не более чем за 2 единицы. Следовательно, diam(G2) = 2

Таким образом, здесь, если бы P была дана n ^-я степень M, то ребра между теми двумя вершинами, которые находятся на n единицах дальше друг от друга, будут добавлены. (если его уже нет в графе G). Таким образом, в общем случае diam(G2) <= ceil( diam(G)/n)

Викторина этого вопроса