 ПОЗНАВАТЕЛЬНОЕ Сила воли ведет к действию, а позитивные действия формируют позитивное отношение Как определить диапазон голоса - ваш вокал Игровые автоматы с быстрым выводом Как самому избавиться от обидчивости Противоречивые взгляды на качества, присущие мужчинам Вкуснейший "Салат из свеклы с чесноком" Натюрморт и его изобразительные возможности Применение, как принимать мумие? Мумие для волос, лица, при переломах, при кровотечении и т.д. Как научиться брать на себя ответственность Зачем нужны границы в отношениях с детьми? Световозвращающие элементы на детской одежде Как победить свой возраст? Восемь уникальных способов, которые помогут достичь долголетия Классификация ожирения по ИМТ (ВОЗ) Глава 3. Завет мужчины с женщиной
Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.
| Построить матрицу фундаментальных разрезов графа. Построить три нефундаментальных разреза графа. 12
Решение:
Так как граф содержит n=8 вершин, то фундаментальных правильных разрезов будет (n+1)=9. Матрица фундаментальных разрезов графа:
Изобразим три нефундаментальных разрезы графа графически:
Произвести раскраску вершин графа, используя функцию Гранди Решение: Функция Гранди g(x) — целочисленная функция, значение которой в вершине xi графа равно отрицательному минимальному числу, не равному значению функции g(x)в вершинах зеркальных xi. Перейдём от орграфа к неографу и раскрасим его с помощью функции Гранди: 1) на графе выбираем (произвольную) вершину x3 и удаляем её; 2) выбираем вершину (смежную с вершиной x3) x5 и красим её в цвет (номер которого минимален и не совпадает с номером окрашенной вершины) — I; 3) вершину x2 —смежную с первыми двумя окрашенными вершинами x3 и x5 — красим её в цвет — номер, которого минимален и не совпадает с номерами цветов окрашенных вершин — II; 4) Более смежных со всеми раскрашенными и удалёнными, нет. 5) (И т.д., т.е.) вершину x4 — II; x1 — I; x6 — IV; x7 — II; x8 — II.
Найти методом точного поиска хроматическое число графа. Решение: Перейдём от орграфа к неографу и построим для его матрицу смежности R:
Так как матрица симметрична относительно главной диагонали, то выражение для определения всех внутренне устойчивых множеств можно находить для половины матрицы. Найдем по методу Магу все Fi , которые содержат вершины, не принадлежащие максимальным внутренне устойчивым множествам Si. Запишем: (1Ú246)(2Ú346)(3Ú45)своё=(12Ú246Ú13456Ú &(34Ú45678Ú36Ú Ú Ú =12347Ú12367Ú134567Ú12345678Ú12345678Ú123468Ú245678=1 F1={x1, x2,x3,x4,x7}, F2={x1,x2,x3,x6,x7}, F3={x1,x2,x3,x6,x8}, F4={пустое},F5={x1,x3,x4,x5,x6,x8}, F6={пустое}, F7={x2,x3,x4,x6,x8},
Для "вершины запишем выражение yjÚykÚ…yn=1 и найдем конъюнкцию этих всех выражений: (цифра это yi) (6Ú7Ú8)(4Ú5)(2Ú3)(1Ú2Ú3Ú6Ú7)(1)(3)(1Ú2Ú4Ú6)=1 своё= =своё
Выбираем любое Yi , которое содержит минимальное число букв: Y1={y1, y2, y5} содержит 3 буквы Þ хроматическое число g(G)=8-3=5. Далее запишем для раскраски графа следующее: y1 ® F1={x1, x2,x3,x4,x7} ÞS1={x5, x6} — эти вершины окрашиваем в цвет “0” y2 ® F2={x1,x2,x3,x6,x7} ÞS2={x4, x5} Þ{x4} — эту вершину окрашиваем в цвет “1” y5 ® F5={x1,x3,x4,x5,x6,x8} ÞS5={x2, x7} — эти вершины окрашиваем в цвет “2” y8 ® F8={x2,x4,x5,x6,x7,x8} ÞS8={x3} — эта вершина окрашиваем в цвет “3” y8 ® F8={x2,x4,x5,x6,x7,x8} ÞS8={x8} — эта вершина окрашиваем в цвет “4” x7как недостающая, получает цвет“5”
Задание №3 Решить задачу коммивояжера для данной матрицы расстояний. (Задача коммивояжера: Коммивояжер должен выехать из заданного города, объехать все остальные города и вернуться назад по кратчайшему маршруту.)
Решение: В клетку с индексом ii ставим символ ¥.Затем с помощью процедуры редукции сначала производим приведение матрицы по строкам, а потом — по столбцам.
Вычеркиваем строку 4 и столбец 1, а в клетку (1,4) ставим символ ¥.
Вычеркиваем строку 2 и столбец 7, а в клетку (7,2) ставим символ ¥.
Вычеркиваем своё.
Далее своё Кратчайший маршрут коммивояжера:
    
Если были альтернативные варианты, то их тоже следует привести и проанализировать. 12 |
