A a, A. Построить на координатной плоскости отношения r и s, если r R, r={(X,y) : X

Пусть G – граф, имеющий, по крайней мере две вершины. Покажите, что G содержит две вершины с одинаковыми степенями

жүктеу/скачать 3.69 Mb. бет 5/5 Дата 15.10.2022 өлшемі 3.69 Mb. #462755

Бұл бет үшін навигация:

• 34. Вычислить кратчайшее расстояние между вершинами s и t.
• 35. Доказать, что следующие свойства графа G эквивалентны: 1) G двусвязен
• 36.Попытайтесь найти плоский граф с пятью гранями, обладающий тем свойством, что любые две его грани имеют общее ребро.
• 37.Найти код дерева методом Пруфера.
• 38. (Теорема о максимальном потоке и минимальном разрезе).
• 41.Планарный граф имеет 12 вершин со степенями 3. Сколько у него ребер и граней Постройте такой граф
• 43. Найти максимальный поток в сети.

32. Пусть G – граф, имеющий, по крайней мере две вершины. Покажите, что G содержит две вершины с одинаковыми степенями. Предположим противное: все вершины графа G имеют разную степень. Максимальная степень вершины в графе порядка n может быть равна (n-1), тогда вершины должны иметь степени (n-1), (n-2), …, 2, 1, 0. Но вершина степени (n-1) соединена со всеми оставшимися вершинами, в том числе и с изолированной, что невозможно => в любом графе обязательно найдутся две вершины, имеющие одинаковую степень. 34. Вычислить кратчайшее расстояние между вершинами s и t. 12 • • 10 2 • 20 6 8 • 4 7 • 3 10 • t s• 20 • 4 s-t = 8+4+4 = 16 35. Доказать, что следующие свойства графа G эквивалентны: 1) G двусвязен, 2) любые две вершины графа G лежат на цикле, 3) любые два ребра лежат на цикле и граф G не имеет изолированных вершин. Доказательство исходит из определения двусвязности (В теории графов двусвязный граф — это связный и неделимый граф, в том смысле, что удаление любой вершины не приведёт к потере связности). По Теореме Уитни, граф двусвязен тогда и только тогда, когда между любыми двумя его вершинами есть минимум два непересекающихся пути =>2 вершины графа принадлежат простому циклу, а это значит, что не имеют изолированных вершин. 36.Попытайтесь найти плоский граф с пятью гранями, обладающий тем свойством, что любые две его грани имеют общее ребро. Так как в графе 5 граней, то в нем одна грань будет внешней, а остальные - нет. Так как любые две грани имеют общее ребро, то в одной компоненте связности должны быть все не внешние грани. Рассмотрим такую компоненту связности графа. Тогда она должна являться плоским графом. Применяем формулу Эйлера для связного плоского графа: f=m-n+2, где f-число граней, m - число ребер компоненты, n - число вершин компоненты => f=5, m=n+3. Для связного плоского графа с n > 3 вершинами и m ребрами справедливо неравенство m<=3n-6, находим n=>5. Без пересечения между ребрами, такой граф не изобразить. 37.Найти код дерева методом Пруфера. 1 2 3 1 2 3 2 3 5 4 5 6 10 11 10 11 4 5 6 1 4 6 7 8 9 11 10 7 8 9 9 8 7 2)321881458 3)153891123 Остальное по аналогии 38. (Теорема о максимальном потоке и минимальном разрезе). Доказать, что в любой сети величина максимального потока из источника s в сток t равна пропускной способности минимального разреза, разделяющего s и t. По т. Форда-Фалкерсона, любой поток между вершинами меньше или равен величине любого сечения. Допустим, существует поток и некоторые сечение. Величина такого поток складывается из величин грузов, проходящих по всем возможным путям из t в s. Каждый такой путь обязан иметь общее ребро с данным сечением, поскольку по каждому ребру нельзя перевести груз больше пропускной способности ребра, поэтому сумма всех грузов меньше или равна сумме пропускных способностей ребер => любой поток равен величине минимального сечения. Разрез графа — множество рёбер, удаление которых делит граф на два изолированных подграфа, один из которых, в частности, может быть отдельным узлом.  Весом разреза называется сумма весов рёбер, проходящих через разрез. Величина максимального потока в графе путей равна величине пропускной способности его минимального разреза. Достаточность: любой поток между вершинами t и s меньше или равен величине любого сечения. 41.Планарный граф имеет 12 вершин со степенями 3. Сколько у него ребер и граней? Постройте такой граф 42. Приведите пример графа являющегося эйлеровым, но не гамильтоновым, а также графа, являющегося гамильтоновым, но не эйлеровым.Что можно сказать о графах, являющихся одновременно эйлеровыми и гамильтоновыми. 43. Найти максимальный поток в сети. 5 b 6 c 6 a 3 3 z 5 d E 6 1 жүктеу/скачать 3.69 Mb. Достарыңызбен бөлісу: