Является ли граф деревом [закрыт]
Хотите улучшить этот вопрос? Переформулируйте вопрос так, чтобы на него можно было дать ответ, основанный на фактах и цитатах.
Закрыт 7 лет назад .
Задачка: Предложите алгоритм, который определяет, является ли граф деревом.
Мое решение, которое, как оказалась, неверное
Думаю, некоторым будет интересно решить 🙂
Дерево — связный граф с n-1 ребром.
Моё решение на Pascal. Граф задаётся матрицей смежности (1 — есть ребро, 0 — иначе). maxV — максимальное число вершин maxE — максимальное число рёбер Храню граф списком рёбер.
Есть несколько способов решения. Можно использовать свойство ацикличности с подсчетом количества вершин, те обходим граф в ширину/глубину, подсчитывая число обойденных вершин, если мы обошли граф и не встретили ни одну вершину два раза, а также общее количество вершин и число обойденных вершин равны, то это дерево .
Выполняем обычный проход по графу и каждую пройденный узел заносим в список, при этом проверяем не содержится ли он в нем уже. Если содержится то всё не дерево 🙂
Дизайн сайта / логотип © 2023 Stack Exchange Inc; пользовательские материалы лицензированы в соответствии с CC BY-SA . rev 2023.3.11.43304
Нажимая «Принять все файлы cookie» вы соглашаетесь, что Stack Exchange может хранить файлы cookie на вашем устройстве и раскрывать информацию в соответствии с нашей Политикой в отношении файлов cookie.
Выберите граф который является деревом
А так хотелось проверять «жлобским методом» 
4 Ответ от rauf 2011-05-08 13:07:22
- Зарегистрирован: 2011-05-05
- Сообщений: 2
We can find it using BFS.
when we reach each node we must increment its degree by one..
if we see that there some nodes with degree >=2 then graph is not tree.
Презентация на тему Деревья
Слайд 1 Факультативный курс
«Деревья»
Учитель информатики ГБОУ СОШ №297 г. Москва ВАГАНОВА Е.В.
Слайд 2 Общие понятия теории графов
Занимательные задачи теории графов
Деревья и их
Содержание
Слайд 3 Общие понятия теории графов
Определение 1. Графом называется совокупность двух множеств:
непустого множества точек (вершин) и множества линий, соединяющих эти точки (ребер).
Иногда каждому ребру графа присваивают некоторое число, которое называется весом данного ребра.
Пример.
Граф с вершинами A, B, C, D, E,
ребрами (A, B), (B, D), (C, E), (E, D).
20 – вес ребра (А, В),
15 – вес ребра (С, Е) и т.д.
Задание.
На каком рисунке точка пересечения
диагоналей не является
вершиной графа?
Слайд 4 Определение 2.
Вершина графа, не принадлежащая ни одному ребру называется
изолированной.
Пример.
Вершина 5 является
изолированной.
Задание.
Вершины графа представляют жителей городка N, а ребра, соединяющие две вершины, — тот факт, что эти люди знакомы. Какую ситуацию изображает приведенный на рисунке граф?
Слайд 5 Определение 3.
Вершина А графа Г, принадлежащая одному ребру, называется
Пример
Вершины А и Б — висячие.
Задание
Укажите висячие вершины.
Есть ли здесь изолированные вершины?
Задание
Начертите граф, содержащий шесть висячих и две изолированные вершины.
Задание
Начертите граф, содержащий шесть висячих и две изолированные вершины.
Слайд 6 Определение 4.
Степенью вершины А графа Г называется количество ребер
графа Г, которым данная вершина принадлежит.
Обозначение : d(A).
Пример
М и N – изолированные вершины. d(M)=.d(N)=0;
для висячей вершины d(A)=d(C)=1.
Задание
В следующих графах найдите степени каждой из вершин.
Ответ:
а) d(1)=d(2)=d(3)=d(4)=d(5)=2; б) d(1)=d(2)=d(4)=1 – висячие вершины,
d(5)=0 – изолированная вершина,
d(3)=2, d(6)=3
Слайд 7 Задание Найдите количество ребер Р графа Г и сумму степеней
С всех его вершин.
Ответ:
Р=4, С=1+2+3+2=8.
Ответ:
Р=5, С=2+3+2+3=10.
Ответ:
Р=1, С=1+1+0=2.
Ответ:
Р=7, С=4+3+2+2+3=14.
Теорема 1.
Сумма степеней вершин графа Г равна удвоенному числу ребер, то есть , где r – число ребер.
Слайд 8 Определение 5.
Пусть дан граф Г с вершинами A1, A
2,…An. Путем в графе Г называется последовательность ребер A1A2, A2A3. An-1An. Вершина A1 -начало пути, вершина An – конец пути.
Пример
(M, B), (B, D), (D, E), (E, C), (C, N) – путь
из вершины М в вершину N.
M – начало пути; N – конец пути.
Задание
Являются ли путями из вершины 1 в вершину 5 следующие последовательности ребер:
А) (1,2),(3,4),(4,5)
Б) (1,2),(2,3),(3,4)
В) (1,2),(2,4),(4,3),(3,2),(2,4),(4,5)
Найдите путь от вершины 1 к вершине 5
Ответ:
(1,2),(2,3),(3,4),(4,5) или (1,2),(2,4),(4,5).
, …,
Слайд 9 Определение 6.
Длиной пути в графе Г называется
количество входящих
в этот путь ребер.
Пример
(M, B), (B, D), (D, E), (E, C), (C, N) –
путь из вершины М в вершину N.
Задание
Укажите все пути,
соединяющие вершины 1 и 4 в графе.
Сколько существует путей
длины два в этом графе?
Ответ:
(1,4) и (1,2),(2,3),(3,4).
Существует восемь путей длины два.
Слайд 10 Определение 7.
Циклом графа Г называется такой путь в этом
графе,
у которого начало совпадает с концом.
Пример
(M, B), (B, D), (D, E), (E, C), (C, N), (N, M)
– цикл в данном графе.
(A, B), (B, D), (D, A) – цикл в данном графе.
Задание
Является ли циклом последовательность ребер:
А) (A,B),(B,E),(E,D),(D,B),(B,A);
Слайд 11 Определение 8. Длиной цикла называется количество входящих в него ребер.
Задание
Для каждого графа назвать все содержащиеся в них циклы и выбрать наибольший и наименьший по длине цикл.
Ответ:
а) (1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,1) – самый длинный цикл; (1,2),(2,6),(6,7),(7,1); (2,3),(3,4),(4,6),(6,2); (1,2),(2,3),(3,4),(4,6),(6,7),(7,1); (2,3),(3,4),(4,5),(5,6),(6,2); (4,5),(5,6),(6,4) – самый короткий цикл;
б) (2,3),(3,5),(5,4),(4,2) – единственный цикл в этом графе;
в) (2,3),(3,5),(5,2) и (2,4),(4,5),(5,2) – самые короткие циклы;
(2,3),(3,5),(5,4),(4,2) – самый длинный цикл.
Можно ли найти путь из вершины 1 в вершину 2 на рисунке б)?
А на рисунке в)?
Слайд 12 Определение 9. Граф называется связным, если между любыми двумя его
вершинами существует путь. В противном случае граф называется несвязным.
Примеры
Чтобы доказать, что граф связный, нужно доказать, что каждые две его вершины являются связными. А чтобы доказать, что граф несвязный – нужно указать в нем две несвязные вершины.
Задание
Какие из графов
являются связными?
Почему?
Слайд 13 Определение 10.
Ребро (А, В) называется мостом графа Г,
если
в графе, полученном после удаления из Г ребра (А, В),
вершины А и В оказываются несвязными.
Задание
Выделите в графе, изображенном на рисунке, ребра, которые являются мостами.
Ответ:
Слайд 14 Теорема 2. Ребро (А, В) является мостом
в том и
только том случае,
если (А, В) – единственный путь,
соединяющий вершины А и В.
Теорема 3. Ребро (А, В) является мостом
в том и только том случае,
если найдутся две вершины С, D
такие, что каждый путь, соединяющий их,
содержит вершины А и В.
Теорема 4. Ребро (А, В) является мостом в том и только том случае, если оно не принадлежит ни одному циклу.
Слайд 15 Задача 1.
Герой произведения Н.В.Гоголя «Мертвые души» Плюшкин из экономии
разрезает каждый лист бумаги на три части. Некоторые из полученных листов он также режет на три части и т.д. Сколько листков бумаги он получит, если разрежет k листов?
K=1 K=2 K=3
Ответ
При разрезании k листов,образуется1+2·k листиков.
Занимательные задачи
теории графов
Слайд 16 Задача 2.
В соревнованиях по шашкам участвует 6 человек: Кирилл, Денис,
Ольга, Сергей, Полина и Андрей. Соревнование проводится по круговой системе – каждый из участников играет с каждым из остальных один раз. К настоящему моменту : Кирилл сыграл с Денисом, Сергеем и Андреем; Денис, с Кириллом и еще с Сергеем; Ольга – с Сергеем, Полиной, Андреем; Сергей – с Кириллом, Денисом и Ольгой; Полина – с Ольгой, а Андрей – с Кириллом и Ольгой. Сколько игр проведено к настоящему моменту и сколько еще осталось?
Ответ.
8
Слайд 17 Задача 3
Чичиков, погостив у Манилова, посетил по одному разу Коробочку,
Ноздрева, Собакевича, Плюшкина, Тентетникова, Бетрищева, Петуха, Констанжогло и Кошкарева в указанном порядке.
Имеется схема расположения имений и соединяющих их дорог. Установить, какое имение кому принадлежит, если ни по одной дороге Чичиков не проезжал более одного раза. Начал свое путешествие Чичиков из дома Манилова, обозначенного на схеме буквой А.
Ответ
А, В, С, D, Е, М, N, Р, К, О.
Слайд 18 Задача4.
В решили поставить спектакль «Ревизор». Разгорелся спор.
— Ляпкиным-Тяпкиным (1)
буду я! – решительно заявил Гена.
— Нет, я буду Ляпкиным-Тяпкиным, — возразил Дима.
— Ну, хорошо, согласен уступить эту роль, если мне дадут сыграть Хлестакова (2), — проявил великодушие Гена.
— …А мне Осипа (3), — не уступил ему в великодушии Дима.
— Хочу быть Земляникой (4) или Городничим (5), сказал Вова.
— Нет, Городничим буду я, — хором закричали Алик и Боря. – Или Хлестаковым, — добавили они одновременно.
Удастся ли распределить роли, чтобы все исполнители были довольны?
Ответ
Слайд 19 Задача5
Жители пяти домов поссорились друг с другом, и, чтобы
не встречаться около колодцев, решили поделить колодцы так, чтобы хозяин каждого дома ходил к «своему» колодцу по «своей» тропинке. Удастся ли им это сделать?
Задача 6
В 5 корзинах лежат яблоки 5 разных сортов. Яблоки первого сорта лежат в корзинах Г и Д; яблоки второго сорта – в корзинах А, Б и Г; в корзинах А, Б и В имеются яблоки пятого сорта; в корзине В имеются к тому же яблоки четвертого сорта, а в корзине Д – третьего. Требуется дать каждой корзине номер, но так, чтобы в корзине №1 были яблоки первого сорта, в корзине №2 – второго и т.д.
Слайд 20 Задача 7.
Являются ли графы на рисунках связными?
Можно ли из этих
графов получить связные графы, добавив1 ребро, 2 ребра?
Ответ:
нет.
а) нет, да; б) да, да; в) нет, нет.
«Кусочки» несвязного графа называют компонентами данного несвязного графа. Чтобы из несвязного графа, содержащего n компонент, получить связный, надо добавить не менее чем (n-1) ребро.
Слайд 21 Задача 8.
«Дорисуйте» граф так, чтобы он стал связным.
Из графа Г сделайте несвязный граф,
удалив а) 2 ребра, б) 1 ребро.
Ответ
а) например,
б) в первом случае невозможно,
а во втором — при удалении ребра
из связного графа новый граф может
оказаться как связным, так и несвязным.
Слайд 22 Деревья и их свойства
Задание 1.
Нарисуйте
А) граф с семью вершинами
и шестью ребрами, не имеющий циклов,
Б) связный граф с семью вершинами и шестью ребрами,
В) граф с семью вершинами, в котором для любых двух вершин существует один и только один связывающий их путь,
Г) связный граф с семью вершинами, каждое ребро которого – мост.
Возможные решения:
Слайд 23 Определение 1. Деревом называется всякий связный граф, не имеющий циклов.
Граф,
состоящий из одной изолированной вершины — дерево.
Задание 2.
Выберите из приведенных ниже графов те, которые являются деревьями. В выбранных деревьях отметьте висячие вершины.
Слайд 24 Задание 3.
Докажите, что для каждой пары вершин дерева существует
единственный соединяющий их путь.
Замечание. Следует :
1) доказать, что для каждой пары вершин дерева существует соединяющий их путь;
2) доказать, что путь, соединяющий любые две вершины дерева, — единственный.
Доказательство.
1) Дерево – связный граф. Из определения связности следует существование пути.
2) Предположим, что существует пара вершин данного дерева, у которых есть два соединяющих их пути. Тогда этот граф содержит цикл, то есть не является деревом. Получили противоречие, следовательно, наше предположение было неверным, и путь, соединяющий любые две вершины дерева, — единственный.
Слайд 25 Задание 4.
Какое максимальное число висячих вершин может иметь дерево, построенное
на 9 вершинах? Какое минимальное число висячих вершин оно может иметь?
Сделайте рисунки таких деревьев.
Ответ:
8 вершин и 2 вершины соответственно.
Слайд 26 Определение 2. Лесом называется несвязный граф, представляющий собой объединение деревьев.
считать, что граф, состоящий из одного дерева – лес.
Задание 5.
Выберите из данных графов те, которые являются лесом.
Ответ:
1) да, 2) да, 3) нет, 4) да.
Слайд 27 Теорема 1. Дерево – это минимальный связный граф.
Задание 6.
Постройте
какие-нибудь деревья с 3, 4, 5, 6 вершинами и посчитайте число ребер в полученных графах.
Возможные варианты ответов:
В любом дереве с 3 вершинами 2 ребра, с 4 вершинами – 3, с 5 вершинами – 4, с 6 вершинами – 5, то есть во всех случаях количество ребер на единицу меньше количества вершин дерева.
Слайд 28 Теорема 2. Число ребер дерева на n вершинах равно n-1.
Следствие.
Связный граф на n вершинах имеет не менее чем n-1 ребро.
Задание 7.
Докажите, что дерево, имеющее не менее двух вершин, содержит, по крайней мере, две висячие вершины.
Доказательство.
Пусть дано дерево D, имеющее n (n≥2) вершин и r ребер. Дерево – связный граф, следовательно, для любой его вершины . Предположим, что для n-1 вершины их степени строго больше 1, а лишь у одной вершины степень больше или равна 1.
Тогда
По теореме 1 сумма степеней всех вершин графа равна 2r, то есть d(A1) + d(A2) +…+ d(An) =2r. Но из теоремы 2 следует, что r=n-1. Значит, =2n-2.
Таким образом, 2n-2>2n-1. Получили противоречие. Значит, по крайней мере две вершины должны иметь степень, равную 1 (по определению они и есть висячие).
Слайд 29 Теорема 3. Последовательность целых чисел d1, d2 , …, dn
является последовательностью степеней вершин некоторого дерева на n вершинах (n≥2) тогда и только тогда, когда:
1) каждое di ≥ 1, I =1, 2, …, n и 2) =2n-2
Задание 8.
Дана последовательность чисел
А) 1, 1, 2, 3, 5, 5, 6; Б) 4, 5, 6, 7; В) 1, 1, 1, 3; Г) 1, 1, 1, 1, 1, 2, 3, 4.
Можно ли построить дерево, такое что данная последовательность чисел являлась бы последовательностью степеней вершин этого дерева?
Ответ:
А) нет, т.к. ≠2n-2,
Б) нет, т.к. нет ни одной висячей вершины,
В) да, т.к. выполняются условия теоремы,
Г) да, т.к. выполняются условия теоремы.
Слайд 30 Остовные деревья
Задача 1.
Лена дружит с Викой, Олей и Сережей,
Сережа, кроме того, – с Машей и Петей, а Глеб – с Димой и Машей. Изобразите с помощью графа отношение «дружить».
В полученном графе выделите те вершины и ребра, которые изображают отношение «Маша дружит с …»
Вопрос :
— Является ли выделенный набор вершин и ребер графом? Почему?
Ответ:
да, состоит из множества точек и множества соединяющих их линий.
Слайд 31 Остовные деревья
Определение 1. Подграфом данного графа Г называется такой граф
Г , что множество его вершин лежит во множестве вершин, а множество его ребер – во множестве ребер исходного графа Г.
Пример 1.
Задание 1.
В приведенных ниже графах назовите несколько подграфов.
Слайд 32 Определение 2. Остовным подграфом графа Г называется такой его подграф,
который содержит все вершины графа Г.
Пример 2.
В графах назовите несколько остовных подграфов.
Слайд 33 Определение 3. Остовной подграф, являющийся деревом, называется остовным деревом.
Пример 3.
Задание 3.
А) Приведите пример графа, из которого нельзя выделить остов.
Б) Приведите пример графа и нескольких его остовных деревьев
Возможные ответы:
Слайд 34 Определение 4. Минимальным остовным деревом называется остовное дерево с минимальным
общим весом его ребер
Задание 4.
В приведенном графе выделите минимальное остовное дерево.
Задание 5.
Из графа Г удалите часть ребер так, чтобы новый граф Г был остовным деревом.
Слайд 35 Задание 6.
Сколько ребер надо удалить из связного графа, имеющего
r ребер и n вершин (r≥n), чтобы получить остов?
Решение.
Остов будет являться деревом на n вершинах. По теореме 2 дерево с n вершинами имеет n-1 ребро. Чтобы из данных r ребер графа получить n-1 ребро, нужно удалить
r-(n-1) или r-n+1 ребро.
Ответ: r-n+1.
Слайд 36 Задачи А. Кэли.
Необходимо соединить n городов железнодорожными линиями так,
чтобы не строить лишних дорог. Известна стоимость строительства для каждой пары городов. Какова должна быть сеть дорог, соединяющая все города и имеющая минимальную возможную стоимость?
В терминах теории графов. Рассмотрим граф Г, в котором вершины – города, ребра – соединяющие пару городов дороги. Каждому ребру назначим вес – стоимость строительства дороги на этом участке.
Нужно построить связный граф, содержащий все вершины, с минимальным весом.
Очевидно, что этот граф должен быть деревом – в противном случае, можно было бы удалить одно ребро, не нарушая связности и уменьшая сумму весов его ребер.
Слайд 37 Правило построения минимального остовного дерева:
Выбрать произвольно вершину Х и отметить
ее.
Среди ребер, выходящих из отмеченной вершины Х, выбрать ребро (Х, Y) c наименьшим весом и включить его в дерево Го.
Повторяя процесс, выполнить поиск наименьшего по весу ребра, соединяющего вершины Х или Y с некоторой другой (непомеченной) вершиной графа Z.
Процесс включения ребер продолжить до тех пор, пока все вершины исходного графа Г не будут включены в дерево Го.
Построенное дерево будет минимальным остовным.
Слайд 38 Задача 2.
Было решено соединить пять городов (Серпухов, Коломну, Каширу,
Москву и Подольск) железнодорожными линиями так, чтобы не строить лишних дорог. Какова должна быть сеть дорог, соединяющая все города и имеющая минимальную возможную стоимость, если известно, что стоимость строительства дороги
от Серпухова до Коломны — 200, до Каширы –100, до Москвы– 75, до Подольска – 80;
от Коломны до Каширы – 150, до Москвы – 120, до Подольска – 140; от Каширы до Москвы -90, до Подольска – 105; от Москвы до Подольска – 60?
Решение.
Затраты на строительство дорог
75+60+90+120=345
Слайд 39 Задача 3.
Задано множество аэродромов, нужно определить минимальный (по сумме
расстояний) набор авиарейсов, позволяющий перелететь с любого аэродрома на любой другой.
Известно, что расстояние между аэродромом А и аэродромом Б равно 500 км, между А и В – 400 км, А и Г – 450 км, А и Д – 670 км, А и Е – 800 км; между аэродромом Б и В – 340 км, Б и Г – 460 км, Б и Д – 550 км, Б и Е – 900 км; между В и Г – 280 км, В и Д – 1100 км, В и Е – 870 км, между Г и Д – 630 км, Г и Е – 1200 км, между Д и Е – 1500 км.
Ответ:
Слайд 40 Задача 4.
Постройте минимальное остовное дерево следующего графа:
Слайд 41 История
Задача о кенигсбергских мостах.
В Кенигсберге 1 есть остров, называемый Кнейпгоф.
Река, омывающая его, делится на два рукава через которые перекинуто семь мостов: а. в, с, d, е, f, g.
Можно ли обойти все эти мосты, не побывав ни на одном из них более раза?
Слайд 42 Решение.
Обобщим задачу: начиная с любой вершины, проходя по каждому
ребру только один раз, вернуться в исходную вершину.
Построим мультиграф, в котором участки суши изобразим как вершины, а дорожки через мосты — как ребра.
Найдем критерий существования обхода (специального маршрута) у данного графа:
граф должен быть связным и каждая его вершина должна быть связана с четным количеством ребер. Полученный граф связный, но не каждая его вершина связана с четным количеством ребер.
Слайд 43 Проблема четырех красок
— математическая задача, предложенная Ф.Гутри (англ.) в
Выяснить, можно ли всякую расположенную на сфере карту раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета.
Слайд 44 Задача сэра Гамильтона (1805-1865)
основная часть задачи — правильный
додекаэдр, сделанный из дерева. Каждая вершина гамильтонова додекаэдра была помечена названием одного из крупных городов — Брюссель, Дели, Франкфурт и т. д.
Задача :
нахождение пути вдоль ребер додекаэдра, проходящего через каждый город в точности по одному разу.
Слайд 45 Задача сэра Гамильтона
Однако такой додекаэдр был слишком громоздким,
и Гамильтон предложил другой вариант своей игры, где многогранник заменялся плоским графом, изоморфным графу, образованному ребрами додекаэдра.
Слайд 46 Леонард Эйлер
Год рождения -1707 .
Место рождения — Базель,
Швейцария
Год смерти — 1783.
Место смерти -Санкт-Петербург, Российская империя.
Гражданство — Швейцария .
Сфера интересов — математика, механика, физика, астрономия .
Слайд 47 Биография .
Леонард Эйлер – великий математик, внесший значительный вклад в
развитие математики, а также механики, физики, астрономии и ряда прикладных наук.
Леонард Эйлер родился в 1707 году в семье базельского пастора, друга семьи Бернулли. Рано обнаружил математические способности. Начальное обучение получил дома под руководством отца, учившегося некогда математике у Якоба Бернулли.
20 октября 1720 года 13-летний Леонард Эйлер стал студентом факультета искусств Базельского университета.
8 июня 1724 года 17-летний Леонард Эйлер произнёс на латыни речь о сравнении философских воззрений Декарта и Ньютона и был удостоен учёной степени магистра.
В начале зимы 1726 года Эйлеру сообщили из Санкт-Петербурга: по рекомендации братьев Бернулли он приглашен на должность адъюнкта по физиологии с окладом 200 рублей. Получение аванса для компенсации проездных расходов растянулось почти на год, и лишь 5 апреля 1727 года Эйлер навсегда покинул родную Швейцарию.
Слайд 48 Публикации
Автор более чем 800 работ по
математическому анализу, дифференциальной геометрии, теории чисел, приближенным вычислениям, небесной механике, математической физике, оптике, баллистике, кораблестроению, теории музыки и др. Многие его работы оказали значительное влияние на развитие науки.
Вклад в науку
Теория графов:задача о Кенигсбергских мостах.
Интересные факты
• Первые русские академики-математики (С. К. Котельников) и астрономы (С. Я. Румовский) были учениками Эйлера.
• Маркиз Кондорсе сообщает, что вскоре после переезда в Берлин Эйлера пригласили на придворный бал. На вопрос королевы-матери, отчего он так немногословен, Эйлер ответил: «Прошу меня простить, но я только что из страны, где за лишнее слово могут повесить».
Слайд 49 Формулы комбинаторики
Слайд 50 Деревья в теории вероятностей
Задача
В урне 2 белых и 4 черных
шара. Один азартный человек держит пари с другим, что среди вынутых 3-ех шаров будет ровно 1 белый. В каком отношении находятся шансы спорящих?
Решение (традиционное).
Испытание — вынимание трех шаров.
Событие «А»- достать ровно один белый и два черных шара.
Число всех исходов
Один белый шар можно достать в С21 случаях , а два черных — С42 , тогда по основному правилу комбинаторики
Отсюда Р(А)=
следовательно Р( ) = 1 — Р( А) = 1 —
Ответ: отношение шансов спорящих равно 3:2.
Слайд 51 Решение (наглядное)
«А»- появление одного белого и двух черных шаров.
Р (А)=
. Р( ) = 1 — Р( А) = 1- .
Ответ: 3:2.
Деревья в теории вероятностей
Слайд 52 Деревья в теории вероятностей
Задача
Слово «МАТЕМАТИКА» разделено на отдельные буквы,
из них произвольным образом отбираются и выкладываются по порядку четыре буквы. Какова вероятность получения слова «МАМА»?
Решение. Составим вероятностное дерево исходов.
Корневая вершина-начало испытания.
Вес ребра — вероятность появления следующей буквы
«А»- вероятность получения слова «МАМА».
Определить, является ли неориентированный graph деревом (ациклический связный graph)
Учитывая неориентированный graph, проверьте, является ли он деревом или нет. Другими словами, проверьте, является ли данный неориентированный graph ациклическим связным graphом или нет.
Например, graph, показанный справа, является деревом, а graph слева не является деревом, так как содержит цикл 0—1—2—3—4—5—0 .
Рекомендуем прочитать:
Дерево — это неориентированный graph, в котором любые две вершины соединены ровно одним путем. Другими словами, любой ациклический связный graph является деревом. Мы можем легко определить ациклический связный graph, выполнив обход DFS на Graphе. Когда мы делаем поиск в глубину из любой вершины v в неориентированном Graph мы можем встретить обратное ребро, указывающее на одного из предков текущей вершины v в дереве ДФС. Каждое “заднее ребро” определяет цикл в неориентированном Graph. Если задний край x —> y , то так как y является предком узла x , у нас есть путь от y к x . Итак, можно сказать, что путь y