Пусть граф g с n вершинами является деревом тогда выберите для g верные утверждения
Добавил пользователь Дмитрий К. Обновлено: 19.09.2024
Деревом называется связный граф без контуров (а значит, и без циклов). Граф (несвязный), состоящий из нескольких деревьев иногда называют лесом.
Напомним, что вершина в графе называется висячей, если ее степень равна единице. Дерево должно обязательно иметь висячую вершину, так как если бы степень всех вершин в дереве была бы больше или равна 2, то по самой первой лемме граф должен иметь цикл, что противоречит определению дерева.
Докажем сейчас следующую достаточно важную теорему.
Теорема. Если граф G является деревом, то число его ребер (т) и число его вершин (п) связаны соотношением т = п – 1.
Доказательство этой теоремы проведем по индукции по числу вершин. Если данный граф содержит всего 2 вершины, то в нем только 1 ребро, и нужное соотношение выполнено. Пусть наше утверждение выполнено для любого дерева, число вершин которого строго меньше п, Докажем его для дерева G, содержащего п вершин. Возьмем висячую вершину дерева G и удалим ее из графа (вместе с единственным ребром, выходящим из этой вершины). Тогда новый граф также является деревом: новый граф не содержит контуров (циклов), он остается связным. (Если бы новый граф оказался несвязным, то какие-то две вершины графа G были бы связаны между собой через удаленную (висячую) вершину. В этом случае степень этой висячей вершины была бы больше или равна 2, что невозможно). Таким образом, новый граф является деревом, и по индукционному предположению для него число ребер меньше числа вершин на единицу. Так как число вершин и число ребер нового графа отличается от числа вершин и ребер “старого” графа G на единицу, то для графа G также выполнено то же самое соотношение. Таким образом, индукция проведена, и теорема доказана.
На самом деле верно и обратное утверждение, которое является частью более общей теоремы, отражающей простейшие свойства дерева.
Теорема. Следующие 4 условия равносильны:
граф G является деревом;
число ребер (т) и число вершин в графе (п) связаны соотношением т = п – 1;
любые две вершины в графе могут быть связаны (простым) путем, и этот путь единствен;
граф G связен и не содержит контуров.
Заметим, что генеалогическое дерево (в котором вершины графа – это некоторый человек и его прямые предки, а смежные вершины – это люди, связанные родством: мать и ее ребенок или отец и его ребенок) деревом в смысле теории графов не является (так как оно обязательно должно содержать циклы: некоторые предки данного человека должны иметь общего предка).
Однако игры с полной информацией (т. е. игры, не имеющие вероятностного характера: шахматы, шашки, уголки и т. д. ) могут быть изображены в виде дерева. Именно поэтому такого типа игры допускают возможность применения компьютеров даже для решения теоретических вопросов этих игр.
Остовное дерево
Деревом называется связный неориентированный граф без циклов.
Существует ещё несколько разновидностей определения дерева:
1. Дерево - это связный граф, у которого число рёбер на 1 меньше числа вершин.
2. Дерево - это связный граф, любые две вершины коотрого соеденены единственной цепью.
3. Дерево - это граф, не содержащий циклов, такой, что при добавлении нового ребра, получаем ровно один цикл.
Остовным деревом неориентированного графа G будем называть его подграф DНG, содержащий все его вершины и являющийся деревом.
Остовное дерево D нагруженного графа G(V,Q,W) называется минимальным, если сумма весов всех его рёбер минимальна по сравнению с другими остовными деревьями.
Остовное дерево связного графа
Определение. Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.
Пусть G связный граф. Тогда остовное дерево графа G (если оно существует) должно содержать n(G) – 1 ребер. Таким образом, любое остовное дерево графа G есть результат удаления из G ровно m(G)-(n(G)-1)=m(G)-n(G)+1 ребер.
Определение. Число m(G)-n(G)+1 называется цикломатическим числом связного графа G и обозначается через v(G).
Замечание. Понятие остовного дерева и цикломатического числа аналогичным образом определяется и для произвольного связного псевдографа G.
Покажем существование остовного дерева для произвольного связного псевдографа G=(V,X), описав алгоритм его выделения.
Шаг 1. Выбираем в G произвольную вершину u1, которая образует подграф G1 псевдографа G, являющийся деревом. Полагаем i=1.
Шаг 2. Если i=n, где n=n(G), то задача решена, и Gi – искомое остовное дерево псевдографа G. В противном случае переходим к шагу 3.
Шаг 3. Пусть уже построено дерево Gi, являющееся подграфом псевдографа G и содержащий некоторые вершины u1, …, ui, где 1didn-1. Строим граф Gi+1, добавляя к графу Gi новую вершину ui+1О V, смежную в G с некоторой вершиной uj графа Gi, и новое ребро (ui+1, uj) (в силу связности G и того обстоятельства, что i
Что входит в перечень работ по подготовке дома к зиме: При подготовке дома к зиме проводят следующие мероприятия.
Основные идеи славянофильства: Славянофилы в своей трактовке русской истории исходили из православия как начала.
Тест по информатике Информационные модели на графах для 6 класса с ответами. Тест включает в себя 2 варианта, в каждом варианте 10 заданий с выбором ответа.
1 вариант
1. Как называется форма информационной модели, которая представляет структуру и состав системы объектов?
1) граф
2) карта
3) план
4) все утверждения верны
2. Какую форму имеет граф?
1) круги, соединённые линиями
2) прямоугольники, соединённые стрелками
3) оба утверждения верны
3. Что обозначают вершины графа?
1) объекты системы
2) связи между объектами
3) процессы в системе
4) все утверждения не верны
4. Чем отличается дуга от ребра графа?
1) дуга и ребро — это одно и то же
2) дуга — направленная линия, ребро — ненаправленная линия
3) ребро — направленная линия, дуга — ненаправленная линия
4) все утверждения не верны
5. Какой граф называется неориентированным?
1) если его вершины не соединены линиями
2) если его вершины соединены дугами
3) если его вершины соединены рёбрами
4) все утверждения не верны
1) Аня-Вера-Галя
2) Аня-Вера-Галя-Аня
3) Даша-Галя-Аня-Галя-Вера
4) все утверждения верны
7. Как называется граф, если его вершины или рёбра дополнены информацией, такой как расстояние или код объекта?
1) взвешенным
2) ориентированным
3) сетью
4) семантической сетью
8. В каком отношении находятся элементы иерархической системы?
1) входят в состав
2) являются разновидностью
3) оба утверждения верны
9. Где у графа-дерева расположен корень?
1) наверху
2) внизу
3) возможны оба варианта
10. Что такое семантическая сеть?
1) граф, в котором вершинам дано подробное название
2) граф, в котором дугам дано описание действий
3) граф, в котором есть дуги, петли и циклы
4) все утверждения верны
2 вариант
1. Какая информационная модель представляет структуру и состав системы объектов?
1) схема
2) граф
3) карта
4) план
2. Как формируется граф?
1) объекты обозначаются кругами или прямоугольниками
2) отношения объектов обозначаются линиями или стрелками
3) выполняются оба утверждения
3. Что называют вершинами графа?
1) процессы в системе
2) объекты системы
3) связи между объектами
4) все утверждения верны
4. Как будут соединены объекты, если отношения симметричны?
1) дугой
2) ребром
3) оба утверждения верны
5. Какой граф называется ориентированным?
1) если его вершины не соединены линиями
2) если его вершины соединены дугами
3) если его вершины соединены рёбрами
4) все утверждения не верны
1) Аня-Вера-Галя
2) Аня-Вера-Галя-Аня
3) Аня-Вера-Галя-Даша
4) все утверждения не верны
7. Какой граф называется сетью?
1) взвешенный
2) ориентированный
3) в котором есть цепи
4) в котором есть циклы
1) иерархическая
2) подчинённая
3) сеть
4) все утверждения не верны
9. Какой вид графа отображает родственные связи между членами семьи?
1) сеть
2) дерево
3) взвешенный граф
10. Можно ли с помощью графа описать рассказ (событие)?
1) да, с помощью любого графа
2) да, с помощью семантической сети
3) нет, граф для этого не предназначен
4) все утверждения не верны
Файл "SAOD_2_kurs_Grafy_3-_treti_pyat_voprosov" внутри архива находится в папке "Вопросы к экзамену с ответами в виде тестирования". Документ из архива "Вопросы к экзамену с ответами в виде тестирования", который расположен в категории "к экзамену/зачёту". Всё это находится в предмете "ооп" из третьего семестра, которые можно найти в файловом архиве РТУ МИРЭА. Не смотря на прямую связь этого архива с РТУ МИРЭА, его также можно найти и в других разделах. Архив можно найти в разделе "к экзамену/зачёту", в предмете "ооп" в общих файлах.
Онлайн просмотр документа "SAOD_2_kurs_Grafy_3-_treti_pyat_voprosov"
Текст из документа "SAOD_2_kurs_Grafy_3-_treti_pyat_voprosov"
Если граф G=(V, E)содержит дугу в виде упорядоченной пары вершин (а, b), то
- это граф ориентированный
- это граф неориентированный
- узел а - начало дуги
- узел b- начало дуги
- узел b- конец дуги
Если граф G=(V, E)содержит дугу в виде не упорядоченной пары вершин (а, b), то
- это граф ориентированный
- это граф неориентированный
- только узел а (а не b)является началом дуги
- можно говорить, что этот граф содержит как дугу ab, так и дугу ba
- только узел b(а не а)является концом дуги
- граф содержит путь из вершины aв вершину b
- граф содержит простой путь из вершины aв вершину b
Пусть орграф G=(V, E)имеет последовательность вершин v1, v2, . v15, для которой существуют дуги вида v1®v2, v2®v3, . vn-1®v15.
Причем нет ни одной петли, а число узлов равно 15. Что можно утверждать о таком графе?
- Данный граф полносвязанный
- Последовательность дуг v1®v2, v2®v3, . vn-1®v15 образует путь длиной 15.
- Данный граф связанный
- Последовательность дуг v1®v2, v2®v3, . vn-1®v15 образует путь длиной 14.
- Последовательность дуг v1®v2, v2®v3, . vn-1®v15 образует простой путь.
- Данный граф содержит цикл.
Пусть дан связанный орграф G=(V, E),причем все дуги имеют неотрицательный вес.Отметьте те алгоритмы (полные варианты, возможно с некоторой адаптацией), которые можно использоватьдля решения следующей задачи: Требуется определить, достижима ли вершина у из вершины х.
- алгоритм получения сильносвязной компоненты на графе
- метод поиска в глубину
- алгоритм нахождение минимального паросочитания на графе
- алгоритм Уоршелла (алгоритм транзитивного замыкания)
Пусть дан связанный орграф G=(V, E),причем все дуги имеют неотрицательный вес.Отметьте те алгоритмы (полные варианты, возможно с некоторой адаптацией), которые можно использоватьдля решения следующей задачи: Требуется определить, достижима ли вершина у из вершины х.
- алгоритм получения сильносвязной компоненты на графе
- алгоритм нахождения максимального покрытия графа
- метод поиска в ширину (волновой метод)
- алгоритм Уоршелла (алгоритм транзитивного замыкания)
Пусть дан связанный орграф G=(V, E),причем все дуги имеют неотрицательный вес.Отметьте те алгоритмы (полные варианты, возможно с некоторой адаптацией), которые можно использовать для решения следующей задачи: Требуется определить кратчайшее расстояние от вершины х до вершины у.
- метод поиска в глубину
- метод поиска в ширину
- алгоритм Уоршелла (алгоритм транзитивного замыкания)
Пусть дан связанный не взвешенный (и непомеченный)орграф G=(V, E).Отметьте те алгоритмы (полные варианты, возможно с некоторой адаптацией), которые можно использовать для решения следующей задачи: Требуется определить кратчайшее расстояние между вершинами х и у.
- метод поиска в глубину
- метод поиска в ширину (волновой метод)
- алгоритм Уоршелла (алгоритм транзитивного замыкания)
Пусть дан связанный орграф G=(V, E),не имеющий петель.Отметьте те алгоритмы (полные варианты, возможно с некоторой адаптацией), которые можно использовать для решения следующей задачи: требуется определить, является ли граф циклическим
- метод поиска в глубину
- метод поиска в ширину
- алгоритм Уоршелла (алгоритм транзитивного замыкания)
Пусть дан связанный неориентированный граф G=(V, E).Отметьте те алгоритмы (полные варианты, возможно с некоторой адаптацией), которые можно использовать для решения следующей задачи: Требуется определить, является ли граф ациклическим.
- алгоритм Прима (на основе контроля одного из свойств остовных деревьев минимальной стоимости)
- алгоритм Крускала (на основе контроля одного из свойств остовных деревьев минимальной стоимости)
- метод поиска в глубину
- метод поиска в ширину (волновой метод)
Пусть дан связанный неориентированный граф G=(V, E).Отметьте те алгоритмы (полные варианты, возможно с некоторой адаптацией), которые можно использовать для решения следующей задачи: определить такой связанный подграф G=(V, E’), чтобы сумма весов дуг принадлежащих Е’, была бы минимальна.
- алгоритм нахождения максимального покрытия графа
- метод поиска в глубину
- метод поиска в ширину
- алгоритм нахождения минимального парасочитания
Пусть дан связанный неориентированный граф G=(V, E).Отметьте те алгоритмы (полные варианты, возможно с некоторой адаптацией), которые можно использовать для решения следующей задачи: построить остовное дерево минимальной стоимости.
- алгоритм нахождения минимального парасочитания
- метод поиска в ширину (волновой метод)
- алгоритм нахождения максимального покрытия графа
Пусть дан граф, педставленый на рис.Укажите результаттопологической сортировки представленного графа (т.е. последовательность вершин после топологической сортировки).
Укажитесвойствасвободных деревьев
- Каждое свободное дерево с числом вершин n, n> 1, имеет в точности n- 1 ребер.
- При добавлении в свободное дерево нового ребра образуется цикл.
- Сумма весов ребер свободного дерева наименьшая на множестве ребер графа
- Свободное дерево представляет собой дерево без корня, ориентированное к листьям
- Каждое свободное дерево является полносвязаннным графом
Связный граф, не имеющий точек сочленения, называется (является) …
- k-связным, причем k>= 2, если между любой парой вершин vиwсуществует не менее kразных путей (k> 1), таких, что, за исключением вершин vиw, ни одна из вершин, входящих в один путь, не входит ни в какой другой из этих путей.
- покрытием графа G= (V, E)
- k-связным, причем k=1
- паросочетанием графаG= (V, E)
Граф называетсяk-связным, если…
- удаление любых k- 1 вершин не приведет к расчленению графа.
- представляет собой свободное дерево
- существует не менее kразличных деревьев в глубинном остовном лесу, построенном методом поиска в глубину
- существует не менее kразличных деревьев в глубинном остовном лесу, построенном методом поиска в ширину
- существует ровно k-1 различных деревьев в глубинном остовном лесу, построенном методом поиска в глубину
- существует не менее k-1 различных путей между двумя любыми вершинами uи v, такие что ни один узел, отличный от узлов uи v(начального и конечного узлов такого пути) не входит в два различных пути.
Деревом называется связный граф без контуров (а значит, и без циклов). Граф (несвязный), состоящий из нескольких деревьев иногда называют лесом.
Напомним, что вершина в графе называется висячей, если ее степень равна единице. Дерево должно обязательно иметь висячую вершину, так как если бы степень всех вершин в дереве была бы больше или равна 2, то по самой первой лемме граф должен иметь цикл, что противоречит определению дерева.
Докажем сейчас следующую достаточно важную теорему.
Теорема. Если граф G является деревом, то число его ребер (т) и число его вершин (п) связаны соотношением т = п – 1.
Доказательство этой теоремы проведем по индукции по числу вершин. Если данный граф содержит всего 2 вершины, то в нем только 1 ребро, и нужное соотношение выполнено. Пусть наше утверждение выполнено для любого дерева, число вершин которого строго меньше п, Докажем его для дерева G, содержащего п вершин. Возьмем висячую вершину дерева G и удалим ее из графа (вместе с единственным ребром, выходящим из этой вершины). Тогда новый граф также является деревом: новый граф не содержит контуров (циклов), он остается связным. (Если бы новый граф оказался несвязным, то какие-то две вершины графа G были бы связаны между собой через удаленную (висячую) вершину. В этом случае степень этой висячей вершины была бы больше или равна 2, что невозможно). Таким образом, новый граф является деревом, и по индукционному предположению для него число ребер меньше числа вершин на единицу. Так как число вершин и число ребер нового графа отличается от числа вершин и ребер “старого” графа G на единицу, то для графа G также выполнено то же самое соотношение. Таким образом, индукция проведена, и теорема доказана.
На самом деле верно и обратное утверждение, которое является частью более общей теоремы, отражающей простейшие свойства дерева.
Теорема. Следующие 4 условия равносильны:
граф G является деревом;
число ребер (т) и число вершин в графе (п) связаны соотношением т = п – 1;
любые две вершины в графе могут быть связаны (простым) путем, и этот путь единствен;
граф G связен и не содержит контуров.
Заметим, что генеалогическое дерево (в котором вершины графа – это некоторый человек и его прямые предки, а смежные вершины – это люди, связанные родством: мать и ее ребенок или отец и его ребенок) деревом в смысле теории графов не является (так как оно обязательно должно содержать циклы: некоторые предки данного человека должны иметь общего предка).
Однако игры с полной информацией (т. е. игры, не имеющие вероятностного характера: шахматы, шашки, уголки и т. д. ) могут быть изображены в виде дерева. Именно поэтому такого типа игры допускают возможность применения компьютеров даже для решения теоретических вопросов этих игр.
Остовное дерево
Деревом называется связный неориентированный граф без циклов.
Существует ещё несколько разновидностей определения дерева:
1. Дерево - это связный граф, у которого число рёбер на 1 меньше числа вершин.
2. Дерево - это связный граф, любые две вершины коотрого соеденены единственной цепью.
3. Дерево - это граф, не содержащий циклов, такой, что при добавлении нового ребра, получаем ровно один цикл.
Остовным деревом неориентированного графа G будем называть его подграф DНG, содержащий все его вершины и являющийся деревом.
Остовное дерево D нагруженного графа G(V,Q,W) называется минимальным, если сумма весов всех его рёбер минимальна по сравнению с другими остовными деревьями.
Остовное дерево связного графа
Определение. Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.
Пусть G связный граф. Тогда остовное дерево графа G (если оно существует) должно содержать n(G) – 1 ребер. Таким образом, любое остовное дерево графа G есть результат удаления из G ровно m(G)-(n(G)-1)=m(G)-n(G)+1 ребер.
Определение. Число m(G)-n(G)+1 называется цикломатическим числом связного графа G и обозначается через v(G).
Замечание. Понятие остовного дерева и цикломатического числа аналогичным образом определяется и для произвольного связного псевдографа G.
Покажем существование остовного дерева для произвольного связного псевдографа G=(V,X), описав алгоритм его выделения.
Шаг 1. Выбираем в G произвольную вершину u1, которая образует подграф G1 псевдографа G, являющийся деревом. Полагаем i=1.
Шаг 2. Если i=n, где n=n(G), то задача решена, и Gi – искомое остовное дерево псевдографа G. В противном случае переходим к шагу 3.
Шаг 3. Пусть уже построено дерево Gi, являющееся подграфом псевдографа G и содержащий некоторые вершины u1, …, ui, где 1didn-1. Строим граф Gi+1, добавляя к графу Gi новую вершину ui+1О V, смежную в G с некоторой вершиной uj графа Gi, и новое ребро (ui+1, uj) (в силу связности G и того обстоятельства, что i
Ограждение места работ сигналами на перегонах и станциях: Приступать к работам разрешается только после того, когда.
Читайте также: