Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015

Автоматическая выдача свидетельства о публикации в официальном СМИ сразу после добавления материала на сайт - Бесплатно

Добавить свой материал

За каждый опубликованный материал Вы получите бесплатное свидетельство о публикации от проекта «Инфоурок»

(Свидетельство о регистрации СМИ: Эл №ФС77-60625 от 20.01.2015)

Инфоурок / Математика / Презентации / Кратчайший путь в графе
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 26 апреля.

Подать заявку на курс
  • Математика

Кратчайший путь в графе

библиотека
материалов
Предположим, что через определенный промежуток времени каждая бактерия либо...
Теория графов Багаева Наталия Витальевна 15.11.2013
Приложении теории графов в различных отраслях наук
Цель: изучить теоретический материал по теме «Теория графов» и возможность ег...
План лекции Введение в теорию графов 1) основные определения; 2) виды графов;...
Определение Графом называется геометрическая фигура состоящая из точек и соед...
ребра называется петлей если его концы совпадают; Определения Пример: Смежны...
степенью вершины A называют количество ребер, для которых она является конце...
Лемма о рукопожатиях В любом графе сумма степеней всех вершин равна удвоенном...
В любом графе число вершин нечетной степени четно Следствие Доказательство:...
Пример: Может ли в государстве, в котором из каждого города выходит 3 дороги...
Виды графов Граф, состоящий из «изолированных» вершин, называется нулевым гр...
граф без кратных ребер и петель называется обыкновенным если степени всех ве...
ориентированные (орграф) Виды графов неориентированные Граф называется ориент...
дуги Начало дуги (A,B) конец дуги(A,B) Степенью входа (выхода) вершины оргра...
Связный граф Если в графе две любые вершины соединены путем, то такой граф на...
Компонента связности - множество вершин такое, что из любой вершины этого мн...
Докажите, что граф с n вершинам, степень каждого из которых не менее , связен...
Интересные дороги Решение:
Паросочетанием в графе называется подграф, в котором все вершины имеют степен...
Свойства паросочетаний чаще всего паросочетания воспринимаются для двудольных...
Путём (или цепью) в графе называется такая последовательность ребер, в которо...
Циклом называется путь, в котором совпадают его начальная и конечная вершины....
Двудольный граф Граф называется двудольным, если его вершины можно разбить на...
Теорема Кенига Граф является двудольным тогда и только тогда, когда он содерж...
Теорема Кенига
Задача о назначениях Дан двудольный граф, требуется построить максимальное па...
Задача о деревенских свадьбах В деревне живут несколько девушек и несколько ю...
Теорема Холла о свадьбах Доказательство: Необходимость: Совершенное паросочет...
Достаточность Пусть G – двудольный граф, для которого |X| = |Y| = n и выполне...
Эйлеровы графы Граф является эйлеровым тогда и только тогда, когда он связный...
Эйлеровым путем в графе называется путь, содержащий все ребра графа. Определе...
Гамильтоновы графы Гамильтонов путем (циклом) графа называется путь ( цикл) п...
Предположим что существует граф G, который удовлетворяет условию теоремы, но...
Планарные (плоские) графы Граф G(V, E) называется планарным, если на плоскост...
Мультиграфом называется граф, в котором пара вершин соединяется несколькими р...
Каждый из 102 учеников одной школы знаком не менее, чем с 68 другими. Докажи...
Город Кенигсберг ( ныне Калининград) расположен на берегах реки Прегель и дву...
Решение: Объекты – части города Связи - мосты Можно ли обойти данный граф пр...
Операции над графами G2 G1 G3 Дополнение графа G1 графом G3, до графа G2 Объ...
Операции над графами Пересечением графов называется граф 	множеством вершин...
Аналитический способ задания графов Граф G(V,E) задан, если задано множество...
Геометрический способ Множество элементов V графа G изображают кружками, это...
44 1

"Инфоурок" приглашает всех педагогов и детей к участию в самой массовой интернет-олимпиаде «Весна 2017» с рекордно низкой оплатой за одного ученика - всего 45 рублей

В олимпиадах "Инфоурок" лучшие условия для учителей и учеников:

1. невероятно низкий размер орг.взноса — всего 58 рублей, из которых 13 рублей остаётся учителю на компенсацию расходов;
2. подходящие по сложности для большинства учеников задания;
3. призовой фонд 1.000.000 рублей для самых активных учителей;
4. официальные наградные документы для учителей бесплатно(от организатора - ООО "Инфоурок" - имеющего образовательную лицензию и свидетельство СМИ) - при участии от 10 учеников
5. бесплатный доступ ко всем видеоурокам проекта "Инфоурок";
6. легко подать заявку, не нужно отправлять ответы в бумажном виде;
7. родителям всех учеников - благодарственные письма от «Инфоурок».
и многое другое...

Подайте заявку сейчас - https://infourok.ru/konkurs

Описание презентации по отдельным слайдам:

№ слайда 1 Предположим, что через определенный промежуток времени каждая бактерия либо
Описание слайда:

Предположим, что через определенный промежуток времени каждая бактерия либо делится на две новые, либо погибает. В скольких случаях n-ое поколение одной бактерии насчитывает ровно k потомков? Закодировать 20 сообщений в виде последовательности длинной 12, состоящей из нулей и единиц; Печатной схемой называют пластинку из какого-либо диэлектрика, на которой в виде металлических полосок вытравлены дорожки. Пересекаться дорожки могут только в определенных точках, куда устанавливаются необходимые элементы, их пересечение в других местах вызовет замыкание электрической цепи. Сконструируете печатную схему Составить структурную формулу метана СН4; Какой метод объединяет данные задачи?

№ слайда 2 Теория графов Багаева Наталия Витальевна 15.11.2013
Описание слайда:

Теория графов Багаева Наталия Витальевна 15.11.2013

№ слайда 3 Приложении теории графов в различных отраслях наук
Описание слайда:

Приложении теории графов в различных отраслях наук

№ слайда 4 Цель: изучить теоретический материал по теме «Теория графов» и возможность ег
Описание слайда:

Цель: изучить теоретический материал по теме «Теория графов» и возможность его применения Задачи: рассмотреть основные определения; сформулировать и доказать основные теоремы, в т.ч. лемму «о рукопожатиях» , теоремы Кёнига, Оре, Холла

№ слайда 5 План лекции Введение в теорию графов 1) основные определения; 2) виды графов;
Описание слайда:

План лекции Введение в теорию графов 1) основные определения; 2) виды графов; II. Основные леммы и теоремы; III. Применение «Теории графов» к решению задач

№ слайда 6 Определение Графом называется геометрическая фигура состоящая из точек и соед
Описание слайда:

Определение Графом называется геометрическая фигура состоящая из точек и соединяющих их линий. Точки называются вершинами. Стороны - ребрами

№ слайда 7 ребра называется петлей если его концы совпадают; Определения Пример: Смежны
Описание слайда:

ребра называется петлей если его концы совпадают; Определения Пример: Смежные ребра: DС и CA, CD и DB, DB и BA, BA и AC Изолированная вершина: E Кратные ребра: m и p Петля: q вершина называется изолированной, если она не является концом ни для одного ребра два ребра называются смежными, если они имеют общую вершину; два ребра называют кратными если они соединяют одну и ту же пару вершин; A B C D E m p s t r q

№ слайда 8 степенью вершины A называют количество ребер, для которых она является конце
Описание слайда:

степенью вершины A называют количество ребер, для которых она является концевой (петли считать дважды) Обозначение: deg(A). deg(E) = 0 deg(C) = 2 E – изолированная вершина deg(G) = 1 deg(H) = 1 deg(E) = 1 deg(B) = 1 deg(A) = 1 deg(C) = 4 deg (D) = 2 G, H, E, B, A - висячие вершины Определения Пример: G H E C D F A B A B C D E u p s t r q

№ слайда 9 Лемма о рукопожатиях В любом графе сумма степеней всех вершин равна удвоенном
Описание слайда:

Лемма о рукопожатиях В любом графе сумма степеней всех вершин равна удвоенному числу ребер Доказательство: Если ребро соединяет две различные вершины графа, то при подсчете суммы степеней всех вершин мы учтем это ребро дважды; Если ребро является петлей, то при подсчете суммы степеней всех вершин мы также учтем это ребро дважды; В любом графе число вершин нечетной степени четно Следствие степенью вершины называют количество ребер, для которых она является концевой (петли считать дважды) |=> (по определению степени вершины) ч.т.д

№ слайда 10 В любом графе число вершин нечетной степени четно Следствие Доказательство:
Описание слайда:

В любом графе число вершин нечетной степени четно Следствие Доказательство: Т.к. каждое ребро инцидентно двум вершинам, в сумму степеней вершин графа каждое ребро вносит двойку. Таким образом, мы приходим к утверждению, которое установлено Эйлером и является исторически первой теоремой теории графов.

№ слайда 11 Пример: Может ли в государстве, в котором из каждого города выходит 3 дороги
Описание слайда:

Пример: Может ли в государстве, в котором из каждого города выходит 3 дороги быть ровно 100 дорог Ответ: не может Решение: Города – вершины графа (k, kєN ). Степень кратности каждой вершины 3 => Дороги – ребра графа (p = 100) По Лемме 3k = 2p. Если р = 100, то k = Но kєN => p ≠ 100

№ слайда 12 Виды графов Граф, состоящий из «изолированных» вершин, называется нулевым гр
Описание слайда:

Виды графов Граф, состоящий из «изолированных» вершин, называется нулевым графом Граф называется полным, если любые две его различные вершины соединены одним и только одним ребром. Граф, в которых не построены все возможные ребра, называют неполным графом. L U B O V M A D B C A B C D E

№ слайда 13 граф без кратных ребер и петель называется обыкновенным если степени всех ве
Описание слайда:

граф без кратных ребер и петель называется обыкновенным если степени всех вершин графа равны, то граф называется однородным. Виды графов 2 2 2 2 3 3 3 3 А B C D deg(A) = deg(B) = deg(C) = deg(D) = 2 deg(O) = deg(P) = deg(E) =deg(K) = 3 A B C D E G

№ слайда 14 ориентированные (орграф) Виды графов неориентированные Граф называется ориент
Описание слайда:

ориентированные (орграф) Виды графов неориентированные Граф называется ориентированным, если некоторые ребра имеют направление. Это означает, что в орграфе некоторая вершина может быть соединена с другой вершиной, а обратного соединения нет. Граф называется неориентированным, если ни одно из ребер не имеет направление.

№ слайда 15 дуги Начало дуги (A,B) конец дуги(A,B) Степенью входа (выхода) вершины оргра
Описание слайда:

дуги Начало дуги (A,B) конец дуги(A,B) Степенью входа (выхода) вершины орграфа называется число ребер, для которых эта вершина является концом (началом) Степень входа вершин графа: Орграф Степень выхода вершин графа: A B C u t s r

№ слайда 16 Связный граф Если в графе две любые вершины соединены путем, то такой граф на
Описание слайда:

Связный граф Если в графе две любые вершины соединены путем, то такой граф называется связным B C D связный граф не связный граф

№ слайда 17 Компонента связности - множество вершин такое, что из любой вершины этого мн
Описание слайда:

Компонента связности - множество вершин такое, что из любой вершины этого множества есть путь в любую другую вершину этого множества, но ни из какой вершины этого множества нельзя попасть в некоторую вершину вне этого множества. Очевидно, что сумма количеств вершин компонент связности равна количеству вершин графа. Определения Максимальный связный подграф графа называется компонентной связности Пример: граф с 10 компонентами

№ слайда 18 Докажите, что граф с n вершинам, степень каждого из которых не менее , связен
Описание слайда:

Докажите, что граф с n вершинам, степень каждого из которых не менее , связен. Рассмотрим вершины A и B, не соединенные путем. Вершина А соединена не менее чем с вершинами, Вершина B также соединена не менее чем с (по условию) Вершина А отлична от В ( иначе между ними существует путь) Тогда в графе 1+1+ + вершин, то есть n+1. Но по условию всего n вершин. Мы пришли к противоречию |=> вершины соединены путем => граф связен. ч.т.д. Решение: Пример: 1 1 A B

№ слайда 19 Интересные дороги Решение:
Описание слайда:

Интересные дороги Решение:

№ слайда 20 Паросочетанием в графе называется подграф, в котором все вершины имеют степен
Описание слайда:

Паросочетанием в графе называется подграф, в котором все вершины имеют степень 1 Подграфом графа G называется граф, у которого все вершины и ребра принадлежат G. Определения Паросочетание называется Совершенным, если оно покрывает все вершины графа, т. е. если каждая вершина графа G инцидентна некоторому ребру данного паросочетания.

№ слайда 21 Свойства паросочетаний чаще всего паросочетания воспринимаются для двудольных
Описание слайда:

Свойства паросочетаний чаще всего паросочетания воспринимаются для двудольных графов паросочетание в графе называются максимальным, если в графе нет паросочетаний с большим числом ребер вершина графа называется насыщенной в паросочетании, если в этом паросочетании существует ребро с концом в этой вершине и свободной в паросочетании если в нем нет такого ребра

№ слайда 22 Путём (или цепью) в графе называется такая последовательность ребер, в которо
Описание слайда:

Путём (или цепью) в графе называется такая последовательность ребер, в которой каждые два соседних ребра имеют общую вершину и никакое ребро не встречается более одного раза. Пример: 1) (А1 А4); (А4 А5) 2) (А1 А2); (А2 А4); (А4 А5). 3) (А1 А4); (А4 А2); (А2 А1); (А1 А3); (А3 А4); (А4, А5). 4) (А1 А4); (А4 А2); (А2 А1); (А1 А3); (А3 А5); путь Определения 1 2 3 4 5 A1 A2 A3 A4 A5

№ слайда 23 Циклом называется путь, в котором совпадают его начальная и конечная вершины.
Описание слайда:

Циклом называется путь, в котором совпадают его начальная и конечная вершины. Простым циклом в графе называется цикл, не проходящий ни через одну из вершин графа более одного раза. Определения Пример: Циклы состоящие из 4 ребер: (AB, BC, CE, EA), (CD, DA, AB, BC) (DA,AB,BE, EC, CA, AE, ED) Простые циклы: (EB, BC, CD, DE) и т.д. A B C D E

№ слайда 24 Двудольный граф Граф называется двудольным, если его вершины можно разбить на
Описание слайда:

Двудольный граф Граф называется двудольным, если его вершины можно разбить на множества Х и У таких, что каждое ребро графа соединяет некоторую вершину из Х с некоторой вершиной из У. Множество Х и У называют долями этого графа Определения Х Y

№ слайда 25 Теорема Кенига Граф является двудольным тогда и только тогда, когда он содерж
Описание слайда:

Теорема Кенига Граф является двудольным тогда и только тогда, когда он содержит более одной вершины и все его циклы имеют четную длину

№ слайда 26
Описание слайда:

№ слайда 27 Теорема Кенига
Описание слайда:

Теорема Кенига

№ слайда 28 Задача о назначениях Дан двудольный граф, требуется построить максимальное па
Описание слайда:

Задача о назначениях Дан двудольный граф, требуется построить максимальное паросочетание Задача о деревенских свадьбах Назначение на должность: имеются вакантные должности и претенденты на них, о каждом претенденте известно какие должности он может занять, требуется заполнить максимум вакансий Выбор представителей: в парламенте есть несколько комиссий, член парламенты может заседать в нескольких комиссиях; нужно выбрать председателя каждой комиссии Пример:

№ слайда 29 Задача о деревенских свадьбах В деревне живут несколько девушек и несколько ю
Описание слайда:

Задача о деревенских свадьбах В деревне живут несколько девушек и несколько юношей. Некоторые юноши знакомы с некоторым девушками. Требуется поженить максимально возможное число пар при условии, что женить можно только знакомые пары Пример:

№ слайда 30 Теорема Холла о свадьбах Доказательство: Необходимость: Совершенное паросочет
Описание слайда:

Теорема Холла о свадьбах Доказательство: Необходимость: Совершенное паросочетание Р в графе G можно рассмотреть как функцию, отображающую каждую вершину из Х в смежную ей вершину Y. По определению совершенного паросочетания эта функция является биекций, откуда |X|=|Y|. Более того, P отображает каждое подмножество M X в некоторое подмножество YM содержащие |M| элементов, являющихся смежными к вершинам из М вершин. Но тогда YM O(M) и |М|=| YM | |O(M)| ч.т.д X1 X2 X3 X4 X5 X6 Y5 Y4 Y3 Y2 Y1 Дан двудольный граф с долями X и Y. Совершенное паросочетание существует тогда и только тогда когда |Х| = |Y| и |O(M)| ≥ |M| для всякого M X

№ слайда 31 Достаточность Пусть G – двудольный граф, для которого |X| = |Y| = n и выполне
Описание слайда:

Достаточность Пусть G – двудольный граф, для которого |X| = |Y| = n и выполнено условие (1). Докажем что в G существует паросочетание P, содержащие n ребер. Проведем индукцией по n. В случае n = 1 (база). Единственная вершина из Х и единственная вершина из Y должны быть соединены ребром, чтобы условие (1) выполнялось. Но тогда можно взять Р = G. Перейдем к шагу индукции: предположим, что для двудольных графов с меньшим чем n числом вершин в каждой доле утверждения теоремы верно. Возможно два случая

№ слайда 32 Эйлеровы графы Граф является эйлеровым тогда и только тогда, когда он связный
Описание слайда:

Эйлеровы графы Граф является эйлеровым тогда и только тогда, когда он связный граф, имеющий все четные вершины

№ слайда 33 Эйлеровым путем в графе называется путь, содержащий все ребра графа. Определе
Описание слайда:

Эйлеровым путем в графе называется путь, содержащий все ребра графа. Определения Эйлеровым циклом или эйлеровой цепью называется цикл, содержащий все ребра графа и притом по одному разу. Если граф G(V,E) обладает эйлеровым циклом, то он связный и все его вершины четные. Теорема №1 Теорема №2 (Эйлер) Граф без изолированных вершин является эейлоровым, тогда и только тогда, когда он связен и степени всех вершин его четны

№ слайда 34 Гамильтоновы графы Гамильтонов путем (циклом) графа называется путь ( цикл) п
Описание слайда:

Гамильтоновы графы Гамильтонов путем (циклом) графа называется путь ( цикл) проходящий через каждую вершину только один раз Граф, содержащий гамильтонов цикл, называется гамильтоновым Пример: гамильтонов путь: (C, D, A, B, M); (B, A, D, C, F) A B C D M F

№ слайда 35 Предположим что существует граф G, который удовлетворяет условию теоремы, но
Описание слайда:

Предположим что существует граф G, который удовлетворяет условию теоремы, но не является гамильтоновым графом. Будем добавлять к нему новые ребра до тех пор, пока не получим максимальный негамильтонов граф G1 Пусть u, v несмежные вершины в полученном графе G1. Если добавить ребро uv, появится гамильтонов цикл. Тогда путь (u, v) – гамильтонов. Для вершин u,v выполняется неравенство: deg u + deg v ≥ n По принципу Дирихле всегда найдутся две смежные вершины t1 и t2 на пути (u, v) т.е. u…t1t2..v, такие что существует ребро ut2 и ребро ut1 |S|+|T| = deg u + deg v ≥ n, но |S|+|T| < n, тогда |S T| = |S|+|T| Теорема (Оре) Доказательство: Пусть дан обыкновенный связный граф, содержащий n > 2 вершин, такой что сумма степеней любых двух несмежных вершин не меньше, чем n. Тогда граф гамильтонов.

№ слайда 36 Планарные (плоские) графы Граф G(V, E) называется планарным, если на плоскост
Описание слайда:

Планарные (плоские) графы Граф G(V, E) называется планарным, если на плоскости его можно изобразить так, чтобы все пересечения его ребер являются вершинами графа G(V, E) первоначальный граф изображенный иначе Грань в плоском представлении графа называется часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов. Пример: (BAC), (CAE), (CDE) A B C D E

№ слайда 37 Мультиграфом называется граф, в котором пара вершин соединяется несколькими р
Описание слайда:

Мультиграфом называется граф, в котором пара вершин соединяется несколькими различными ребрами. Для ориентированного мультиграфа вершины могут соединятся несколькими ребрами в каждом из направлений. Мультиграф A B C Псевдографом называется граф, в котором есть и петли и кратные ребра A C B

№ слайда 38 Каждый из 102 учеников одной школы знаком не менее, чем с 68 другими. Докажи
Описание слайда:

Каждый из 102 учеников одной школы знаком не менее, чем с 68 другими. Докажите, что среди них найдутся четверо, имеющие одинаковое число знакомых 1) пусть верно обратное. 2) тогда для каждого числа от 68 до 101 имеется не более трех человек, имеющих такое же число знакомых. 3) имеется ровно 34 натуральных числа, начиная с 68 и заканчивая 101, а 102 = 3 ∙ 4. Это означает что для каждого числа от 68 до 101 есть ровно три человека, имеющие такое число знакомых 4) Но тогда количество людей, имеющих нечетное количество знакомых нечетно. (Л) | => верно обратное, т.е. среди учеников найдутся четверо, имеющие одинаковое число знакомых Решение: Пример:

№ слайда 39 Город Кенигсберг ( ныне Калининград) расположен на берегах реки Прегель и дву
Описание слайда:

Город Кенигсберг ( ныне Калининград) расположен на берегах реки Прегель и двух островах на этой реке. Части города соединены мостами. Спрашивается, можно ли, выйдя из какой либо точки города, пройти по каждому мосту ровно один раз и вернутся в исходную точку Задача о кёнигсберских мостах

№ слайда 40 Решение: Объекты – части города Связи - мосты Можно ли обойти данный граф пр
Описание слайда:

Решение: Объекты – части города Связи - мосты Можно ли обойти данный граф пройдя по каждому ребру ровно один раз и вернуться и вернувшись в исходную вершину, то есть существует ли последовательность ребер графа со следующими свойствами: любые два соседних ребра имеют общую вершину; последнее ребро имеет общую вершину с первым; каждое ребро графа встречается в последовательности ровно один раз

№ слайда 41 Операции над графами G2 G1 G3 Дополнение графа G1 графом G3, до графа G2 Объ
Описание слайда:

Операции над графами G2 G1 G3 Дополнение графа G1 графом G3, до графа G2 Объединением графов при условии, что называется граф множеством вершин которого является множество а множеством его ребер является множество Дополнением графа G1 (V1,E1) называется граф множеством вершин которого является множество V1, а множеством его ребер является множество

№ слайда 42 Операции над графами Пересечением графов называется граф 	множеством вершин
Описание слайда:

Операции над графами Пересечением графов называется граф множеством вершин которого является множество а множеством его ребер – множество Суммой по модулю два графа при условии, что называется граф множеством вершин которого является множество а множеством его ребер – множество Другими словами, этот граф не имеет изолированных вершин и состоит только из ребер, присутствующих либо в первом графе, либо во втором, но не в обоих графах одновременно.

№ слайда 43 Аналитический способ задания графов Граф G(V,E) задан, если задано множество
Описание слайда:

Аналитический способ задания графов Граф G(V,E) задан, если задано множество элементов V и отображение Е множества V в V. Отображение Е может быть как однозначным, так и многозначным. В общем случае на V и E никаких ограничений не накладывается. Способы задания графов Пусть дано множество { } , которое имеет мощность . Вместо { } иногда пишут { }, { }. Для того чтобы задать отображение Е на V или, что то же самое, отображение V в V, необходимо каждому элементу поставить в соответствие Е. Это подмножество обозначают через поэтому Другой формой аналитического способа задания является задание графа как совокупности множества элементов V и подмножества упорядоченных пар Подмножество множества пар декартова произведения эквивалентно бинарному отношению R, заданному на множестве V. Поэтому множество V и бинарное отношение R на множестве V также определяет некоторый граф G.

№ слайда 44 Геометрический способ Множество элементов V графа G изображают кружками, это
Описание слайда:

Геометрический способ Множество элементов V графа G изображают кружками, это множество вершин. Каждую вершину соединяют линиями с теми вершинами , для которых выполняется условие . Множество линий, которое соответствует множеству упорядоченных пар , есть множество ребер графа. Матричный способ Квадратная матрица элементами которой являются нули и единицы, а также некоторое число m, называется матрицей смежности графа G(V,E) тогда и только тогда когда ее элементы образуются по следующему правилу: элемент стоящий на пересечении столбца, равен единице, если имеется ребро, идущие из вершины в вершину , и равен нулю в противном случае. Элемент равен единице, если при вершине имеется петля, и равен нулю в противном случае. Элемент равен некоторому числу m, где m – число ребер графа, идущее из вершины в вершину . Пусть - вершины, а - ребра некоторого ориентированного графа G(V,E). Матрица размером (m x n), где называется матрицей инцидентности для ориентированного графа.

Краткое описание документа:

Граф, или неориентированный граф  — это упорядоченная пара , где  — это непустоемножество вершин или узлов, а  — множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами.

 (а значит и, , иначе оно было бы мультимножеством) обычно считаются конечными множествами. Многие результаты, полученные для конечных графов, неверны (или каким-либо образом отличаются) длябесконечных графов, поскольку не все утверждения, имеющие место для конечных совокупностей, выполняются в случае бесконечных множеств.

Вершины и рёбра графа называются также элементами графа, число вершин в графе  — порядком, число рёбер  —размером графа.

Вершины  и  называются концевыми вершинами (или просто концами) ребра . Ребро, в свою очередь,соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.

Два ребра называются смежными, если они имеют общую концевую вершину.

Два ребра называются кратными, если множества их концевых вершин совпадают.

Ребро называется петлёй, если его концы совпадают, то есть .

Степенью  вершины  называют количество инцидентных ей рёбер (при этом петли считают дважды).

Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.

Автор
Дата добавления 27.05.2015
Раздел Математика
Подраздел Презентации
Просмотров800
Номер материала 546404
Получить свидетельство о публикации

Идёт приём заявок на международный конкурс по математике "Весенний марафон" для учеников 1-11 классов и дошкольников

Уникальность конкурса в преимуществах для учителей и учеников:

1. Задания подходят для учеников с любым уровнем знаний;
2. Бесплатные наградные документы для учителей;
3. Невероятно низкий орг.взнос - всего 38 рублей;
4. Публикация рейтинга классов по итогам конкурса;
и многое другое...

Подайте заявку сейчас - https://urokimatematiki.ru


Выберите специальность, которую Вы хотите получить:

Обучение проходит дистанционно на сайте проекта "Инфоурок".
По итогам обучения слушателям выдаются печатные дипломы установленного образца.

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ


"Инфоурок" приглашает всех педагогов и детей к участию в самой массовой интернет-олимпиаде «Весна 2017» с рекордно низкой оплатой за одного ученика - всего 45 рублей

В олимпиадах "Инфоурок" лучшие условия для учителей и учеников:

1. невероятно низкий размер орг.взноса — всего 58 рублей, из которых 13 рублей остаётся учителю на компенсацию расходов;
2. подходящие по сложности для большинства учеников задания;
3. призовой фонд 1.000.000 рублей для самых активных учителей;
4. официальные наградные документы для учителей бесплатно(от организатора - ООО "Инфоурок" - имеющего образовательную лицензию и свидетельство СМИ) - при участии от 10 учеников
5. бесплатный доступ ко всем видеоурокам проекта "Инфоурок";
6. легко подать заявку, не нужно отправлять ответы в бумажном виде;
7. родителям всех учеников - благодарственные письма от «Инфоурок».
и многое другое...

Подайте заявку сейчас - https://infourok.ru/konkurs

Похожие материалы

Включите уведомления прямо сейчас и мы сразу сообщим Вам о важных новостях. Не волнуйтесь, мы будем отправлять только самое главное.
Специальное предложение
Вверх