В графе найти максимальное (по количеству ребер) подмножество попарно несмежных ребер.
Заказать уникальную курсовую работу- 11 страница
- 0 + 0 источников
- Добавлена 01.06.2010
- Содержание
- Часть работы
- Список литературы
- Вопросы/Ответы
Подмножество попарно несмежных ребер графа является максимальным, если при добавлении хотя бы одного ребра исходного графа полученное подмножество будет содержать смежные ребра.
Будем строить требуемое максимальное подмножество, добавляя к полученному множеству дополнительные, не принадлежащие ему ребра и выясняя, сохраняется ли условие попарной несмежности ребер.
Сделаем это на примере следующего графа:
Граф состоит из 4 ребер: {1, 3}, {1, 4}, {3, 4}, {2, 4}
Искомое подмножество пока пусто.
Добавляем к искомому подмножеству первое ребро графа {1, 3} и проверяем, что все ребра подмножества попарно несмежны. В случае одного ребра это выполнение этого условия очевидно.
Добавляем второе ребро и проверяем подмножество, состоящее из ребер {1, 3} и {1, 4}. Вновь добавленное ребро нарушает условие несмежных ребер (вершина 1 общая), поэтому удаляем его из искомого подмножества. Полученное на этом шаге подмножество {1, 3}.
Добавляем ребро {3, 4}. Условие несмежных ребер опять нарушено (вершина 3 общая). Удаляем ребро. Полученное на этом шаге подмножество опять состоит из одного ребра {1, 3}.
Добавляем ребро {2, 4}. Ребра {1, 3} и {2, 4}, из которых состоит подмножество, несмежны, поэтому оставляем вновь добавленное ребро. Удаляем ребро. Полученное на этом шаге подмножество опять состоит из одного ребра {1, 3}. Полученное на этом шаге подмножество состоит из двух ребер {1, 3}, {2, 4}.
Поскольку в исходном графе не осталось непроверенных ребер, полученный на последнем шаге результат и есть искомое максимальное подмножество попарно несмежных ребер графа.
Удаляем ребро. Полученное на этом шаге подмножество опять состоит из одного ребра {1, 3}. Полученное на этом шаге подмножество состоит из двух ребер {1, 3}, {2, 4}.
Поскольку в исходном графе не осталось непроверенных ребер, полученный на последнем шаге результат и есть искомое максимальное подмножество попарно несмежных ребер графа.
1
2
3
4
Вопрос-ответ:
Что такое подмножество попарно несмежных ребер?
Подмножество попарно несмежных ребер - это такое подмножество ребер графа, в котором все ребра не имеют общих конечных вершин.
Как найти максимальное по количеству ребер подмножество попарно несмежных ребер в графе?
Для того чтобы найти максимальное по количеству ребер подмножество попарно несмежных ребер в графе, можно использовать алгоритм перебора. Алгоритм заключается в добавлении к полученному множеству дополнительных, не принадлежащих ему ребер и проверке сохранения свойства попарной несмежности ребер при добавлении каждого нового ребра.
Почему подмножество попарно несмежных ребер графа является максимальным?
Подмножество попарно несмежных ребер графа является максимальным, если при добавлении хотя бы одного ребра исходного графа полученное подмножество будет содержать смежные ребра. Это связано с тем, что добавление любого ребра, имеющего общую вершину с уже существующими ребрами, нарушит свойство попарной несмежности.
Как построить требуемое максимальное подмножество попарно несмежных ребер?
Для построения требуемого максимального подмножества попарно несмежных ребер графа, необходимо начать с пустого множества и последовательно добавлять к нему дополнительные, не принадлежащие ему ребра. При этом после каждого добавления нужно проверять сохранение свойства попарной несмежности ребер. Если свойство нарушается, ребро не добавляется, в противном случае оно добавляется в множество.
Какой алгоритм использовать для отыскания максимального подмножества попарно несмежных ребер?
Для отыскания максимального подмножества попарно несмежных ребер в графе, можно использовать алгоритм перебора. Этот алгоритм заключается в последовательном переборе всех возможных комбинаций ребер и проверке сохранения свойства попарной несмежности при добавлении каждого нового ребра. Алгоритм останавливается, когда больше нельзя добавить ни одно ребро, сохраняя при этом свойство попарной несмежности у всех ребер в подмножестве.
Зачем нужно находить максимальное подмножество попарно несмежных ребер в графе?
Нахождение максимального подмножества попарно несмежных ребер в графе может быть полезным для решения различных задач, таких как оптимизация сетей передачи данных, построение расписания и других.
Какое подмножество считается максимальным в данной задаче?
Подмножество попарно несмежных ребер графа является максимальным, если при добавлении хотя бы одного ребра исходного графа полученное подмножество будет содержать смежные ребра. Иначе говоря, в максимальном подмножестве не может быть добавлено ни одно ребро, которое соединяет вершины, уже присутствующие в этом подмножестве.
Каким образом строится требуемое максимальное подмножество попарно несмежных ребер?
Мы строим требуемое максимальное подмножество попарно несмежных ребер путем добавления к уже полученному множеству дополнительных ребер, которые не принадлежат ему. При этом, мы проверяем, чтобы добавляемые ребра не создавали новых смежных ребер в этом подмножестве. Таким образом, мы постепенно наращиваем максимальное подмножество.
Как определить, что подмножество является максимальным?
Подмножество попарно несмежных ребер считается максимальным, если в него невозможно добавить ребро из исходного графа без образования смежных ребер. То есть, если при попытке добавить новое ребро в максимальное подмножество, оно будет смежным с уже выбранными ребрами, то подмножество перестанет быть максимальным.
Как найти максимальное по количеству ребер подмножество попарно несмежных ребер в графе?
Для того чтобы найти максимальное по количеству ребер подмножество попарно несмежных ребер в графе, можно применить алгоритм перебора. Подмножество попарно несмежных ребер графа является максимальным, если при добавлении хотя бы одного ребра исходного графа полученное подмножество будет содержать смежные ребра. Алгоритм заключается в строительстве требуемого максимального подмножества путем добавления к полученному множеству дополнительных, не принадлежащих ему ребер и выяснения сохранения требуемых свойств.