0: Здравствуйте, ребята. Начиная с этого урока мы с вами начинаем изучение темы, введение в теорию Графов. Тема эта совсем небольшая, всего 4 урока, но в ней вы познакомитесь с графами.
1: Научитесь решать с помощью Графов несложные задачи. Тема этого урока граф вершина ребро представление задачи с помощью графа.
2: Сегодня мы с вами изучим основные понятия теории Графов, а именно граф вершина, графа ребро, графа степень вершины графа, а также вы узнаете, что такое в графе, а также начнём.
3: Формирование умений и представление представлять задачи в виде графа.
4: Но для начала немного русского языка граф это не граф, хотя оба эти слова образованы от латинского слова графио граф.
5: О котором мы будем говорить с вами на уроках теории вероятности. Это граф, схема.
6: А вот с понятием граф как титул вы знакомитесь на уроках истории?
7: Вообще, граф, это схема, отображающая отношения между объектами задачи. Давайте рассмотрим пример.
8: Например, электрическая цепь, которую вы видите на этом рисунке.
9: И фрагмент карты, который вы видите на этом рисунке, могут быть отображены в виде простой схемы, на которой мы обозначим точками.
10: Или называем ещё их вершинами основные объекты этих 2 задач, а также с помощью линий соединим эти точки полу.
11: Диаграмма и будет называться граф.
12: Все.
13: Элементы графа называются так вершины с помощью вершин мы показываем, мы изображаем объекты нашей задачи в да.
14: Графе вершин 5 т, п, ку с р.
15: Линии, которые соединяют вершины графа и показывают отношения между объектами нашей задачи, называют ребра.
16: В данном случае в данной задаче рёбер у нас гораздо больше, чем у меня показано, и все же назову некоторые из них т. П. П у т.
17: С р q r но на самом деле есть ещё у нас ребро у с п с т у.
18: В данном случае граф не ориентирован, и мы видим, что все линии, соединяющие вершины нашего графа, изображаются именно как не напра.
19: Это ребра, а бывают графы, направленные в которых вот эти связи изображаются в виде стрелок, и тогда они называются дуги. Но об этом мы будем го.
20: Говорить с вами позже.
21: У каждой вершины графа есть характеристика, и называется эта вершина степень степенью вершины называется число рёбер, концом которых является эта вершина, например.
22: Вот эта вершина п имеет степень 3, потому что она является концом для сразу 3, а вершина ку и вершина с имеет степень 4.
23: Потому что в них соединяется по 4 ряда.
24: Вообще, теория Графов это довольно обширный раздел дискретной математики, в котором системно изучаются свойства Графов теория Графов очень широко применяется в решении экономических и управленческих задач.
25: Программировании, химии, конструировании и изучении электрических цепей, коммуникации, психологии, социологии, лингвистики и других областях. Поэтому изучение теории гра
26: Перенесено в школу, и уже в школе мы знакомимся с этой теорией, учимся её применять и решать простейшие задачи. Давайте рассмотрим некоторые примеры.
27: Как же могут выглядеть графы граф номер, вот этот граф, в котором мы видим 4 вершины, обозначенные окружностями, и связи, линии, соединяющие эти окружности необязательно.
28: Оказывается, ребята, изображать вот такими огромными большими окружностями. Нужно достаточно изобразить вершины точками и соединить линиями. Здесь вершины поименованы, а вот в этом графе не поименованы и
29: Даже генеалогическое дерево это тоже своеобразный граф, граф вашей семьи.
30: Давайте рассмотрим несколько задач, которые решаются с использованием Графов и облегчают решение. Я вам это докажу. Итак, задачи Андрей, Борис, Виктор и Григорий.
31: Шахматы каждый сыграл с каждым по 1 партии. Сколько партий было сыграно? Ну скажете вы, что же, сложного в этой задаче достаточно выписать все пары? Действительно можно выписать все пары Андрей Бори.
32: Андрей, Виктор, Андрей, Григорий, Борис, Виктор, Борис, Григорий и Григорий, Виктор, Григорий. Вот у нас всего получилось 6 пар без повторений и можно смело утвер.
33: Ждать, что было сыграно 6 партий, но эту задачу можно было бы представить в виде графа и решить её ещё проще без выписывания мы можем представить себе наших шахматистов как вершины.
34: А. Б. В г и соединив их линиями, рёбрами, увидев, увидеть, сколько всего было пар образовано, теперь нам нужно только посчитать наши ребра это то.
35: Будет 6. 1, 2, 3, 4, 5 и 6.
36: Но существуют задачи немножечко более сложные посмотрите, задача похожа, но чуть чуть изменена Андрей, Борис, Виктор и Григорий после возвращения из спортивного лагеря подарили на память друг другу свои фотографии.
37: Причём каждый мальчик подарил каждому по 1 фотографии, сколько было всего фотографий подарено.
38: Правда, похожа задача, но решение несколько другое. Предположите.
39: Сколько было подарено фотографий, давайте рассмотрим. Итак, посмотрите, граф для решения этой задачи похож на предыдущий, но здесь все ребра заменены стрелками, причём
40: Стрелки имеют 2 направления, это дуги, дуги, но на самом то деле вот где видим двунаправленную стрелку, это 2 разных стрелки, которые направлены в разные направления, просто в разные стороны и
41: Вот для того, чтобы посчитать, сколько было фотографий, нам как раз и пригодится понимание степени вершины, ведь каждый мальчик получил фотографии от каждого мальчика, то есть Андрей получил Ровно.
42: На 3 фотографии и Борис получил Ровно 3 фотографии, и Григорий 3 фотографии, и Виктор получил 3 фотографии, итого 4 мальчика каждый получил по 3 фотографии 12 фо.
43: Да, и если мы с вами сейчас посчитаем просто количество стрелок, количество рёбер, считая дуг, считая, что здесь по 2 дуги, то мы тоже придём к этому же самому числу двена.
44: Фотографии и выписывать ничего не нужно. И по рисунку мы с вами нашли решение. Есть, конечно, задачи, которые сразу же поставлены, условия которых сразу поставлено на
45: Они так и называются задачи на графах рассмотрим несколько простейших задач на рисунке схема дорог, связывающих города а б в и г. По каждой дороге можно двигаться только в 1 направлении.
46: Указанном стрелкой, сколько существует различных путей из города. А в город б. Вот здесь, ребята, задача поставлена на ориентированном графе. Видите здесь все
47: Связи обозначены стрелками или, говорят ееще дугами можно, конечно, выписать в этом графе не так уж много дорог а б г а с а г и а в.
48: Г всего 3 дороги, но это видно и по графу без выписывания. Также напомню вам, что можно посчитать
49: Степень каждой вершины и сумма степеней у нас будет как раз равна общему количеству путей в пункт город б можно добраться только 1 путём.
50: 1 путём.
51: Не хочет писать вот так 1 в город в можно добраться только 1 путём.
52: И из города, а можно тоже 1 путём было добираться. Итого в город г мы можем добраться 1 + 1 + 1 3 путями.
53: Возьмём, рассмотрим эту же задачу, только немножечко усложним. А вот здесь у меня ошибка, ребята, здесь надо букву г написать. Нет у меня города её усложним немножечко эту задачу. И давайте тоже решим её. Можем
54: Выписать все пути для того, чтобы проверить себя а. Б г а б в г а г и а в г.
55: Всего 4 пути насчитали. Можем проверить наши предположения о количестве путей в графе, которое равно сумме степеней вершин. Итак, у вершины b степень 1, потому что
56: То в неё можно добраться только 1 путём у вершины в степень 2, потому что в неё можно добраться 2 путями в вершину г. Мы можем добраться из вершины b, из вершины в.
57: И ещё 1 путём из вершины а и таким образом, если мы посчитаем сумму степеней этих вершин, то мы получим, что в вершину г из а мы можем добраться 4.
58: Ну и ещё более сложная задача, которая вообще выписыванием не имеет смысла решать, а имеет смысл решать только с помощью нашей нашего предположения.
59: О том, что у нас сумма путей равна сумме.
60: Степеней вершин. Здесь 2 в ж мы можем добраться из б и из г. Получается 1 + 2.
61: 3 в. Д. Мы можем добраться только из г.
62: Получается, 2 путями и в её мы можем добраться пятью путями 3 + 2. Попробуйте посчитайте, выпишите все пути и проверьте моё решение. Ну что ж.
63: Друзья мои, пришло время домашнего задания. Вам самостоятельно нужно будет решить 2 задачи для решения этих задач. Нужно будет построить графы. Напоминаю вам, что
64: Граф может служить любая геометрическая фигура, и окружность, и овал, и квадрат, и круг, и даже просто жирная точка при встрече каждый из друзей пожал руку каждому другу сколько?
65: Было рукопожатие сделано, если друзей было трое, четверо и пятеро. То есть решение этой задачи у вас будет 3 графа. На 1 будет 3 вершины и все связи, которые только могут быть на 2. Гра.
66: Будет 4 вершины и все связи, которые только могут быть и на 4. На 3 графе будет 5 вершин. И все связи в ответе у вас также будет 3 числа. 2 задача по
67: Окончании деловой встречи специалисты обменялись визитными карточками. Каждый вручил свою карточку каждому, сколько всего визитных карточек было роздано, если во встрече участвовали 3, 4 и 5 человек, здесь граф уже
68: У нас будет ориентированный, а точнее у нас будут связи двойные двойными стрелками, и вам тоже нужно будет составить 3 различных графа с различным количеством вершин 3, 4 и 5.
69: И посчитать, сколько всего у нас связей будет между этими вершинами. Желаю вам удачи. Все у вас получится фото выполненного задания присылайте н.
70: Но если вы очень хотите, то вы можете выполнить это задание на компьютере, используя встроенный графический редактор в текстовый процесс, либо нарисовать реше.
71: Удачи.