» » » Граф и его элементы. Основные определения

Презентация на тему Граф и его элементы. Основные определения


Здесь Вы можете скачать готовую презентацию на тему Граф и его элементы. Основные определения. Предмет презентации: Математика. Красочные слайды и илюстрации помогут вам заинтересовать своих одноклассников или аудиторию. Для просмотра содержимого презентации воспользуйтесь плеером, или если вы хотите скачать презентацию - нажмите на соответствующий текст под плеером. Презентация содержит 21 слайд.

Слайды презентации

Слайд 1
Граф и его элементы Основные определения
Слайд 2
 Переход по слайдам осуществляется только по нажатию левой кнопки мыши клик мыши!!!  Если есть мигающая стрелка, значит нужно нажатие левой кнопки мыши в любом месте слайд для продолжения презентации!!!!  После прочтения удалить слайд!
Слайд 3
Г Р А Ф О М G = ( V , X ) Н А З Ы В А Е Т С Я П А Р А Д В У Х К О Н Е Ч Н Ы Х М Н О Ж Е С Т В : М Н О Ж Е С Т В О Т О Ч Е К И М Н О Ж Е С Т В О Л И Н И Й , С О Е Д И Н Я Ю Щ И Х Н Е К О Т О Р Ы Е П А Р Ы Т О Ч Е К . Впервые понятие «граф» ввел в 1936 г. венгерский математик Денни Кёниг . но первая работа по теории графов принадлежала перу великого Леонарда Эйлера и была написана еще в 1736 г.
Слайд 4
Т О Ч К И Н А З Ы В А Ю Т С Я В Е Р Ш И Н А М И , И Л И У З Л А М И , Г Р А Ф А , Л И Н И И – Р Е Б Р А М И Г Р А Ф А .
Слайд 5
Е Е С С Л Л И И Р Р Е Е Б Б Р Р О О Г Г Р Р А А Ф Ф А А С С О О Е Е Д Д И И Н Н Я Я Е Е Т Т Д Д В В Е Е Е Е Г Г О О В В Е Е Р Р Ш Ш И И Н Н Ы Ы , , Т Т О О Г Г О О В В О О Р Р Я Я Т Т , , Ч Ч Т Т О О Э Э Т Т О О Р Р Е Е Б Б Р Р О О И И М М И И Н Н Ц Ц И И Д Д Е Е Н Н Т Т Н Н О О . . Д Д В В Е Е В В Е Е Р Р Ш Ш И И Н Н Ы Ы Г Г Р Р А А Ф Ф А А Н Н А А З З Ы Ы В В А А Ю Ю Т Т С С Я Я С С М М Е Е Ж Ж Н Н Ы Ы М М И И , , Е Е С С Л Л И И С С У У Щ Щ Е Е С С Т Т В В У У Е Е Т Т И И Н Н Ц Ц И И Д Д Е Е Н Н Т Т Н Н О О Е Е И И М М Р Р Е Е Б Б Р Р О О . .  Н Н А А Р Р И И С С У У Н Н К К Е Е С С М М Е Е Ж Ж Н Н Ы Ы М М И И Я Я В В Л Л Я Я Ю Ю Т Т С С Я Я В В Е Е Р Р Ш Ш И И Н Н Ы Ы A A и и B B , , A A и и C C ; ; С С М М Е Е Ж Ж Н Н Ы Ы М М И И Я Я В В Л Л Я Я Ю Ю Т Т С С Я Я Р Р Е Е Б Б Р Р А А c c и и d d , , a a и и b b . .  Е Е С С Л Л И И Г Г Р Р А А Ф Ф И И М М Е Е Е Е Т Т Р Р Е Е Б Б Р Р О О , , У У К К О О Т Т О О Р Р О О Г Г О О Н Н А А Ч Ч А А Л Л О О И И К К О О Н Н Е Е Ц Ц С С О О В В П П А А Д Д А А Ю Ю Т Т , , Т Т О О Э Э Т Т О О Р Р Е Е Б Б Р Р О О Н Н А А З З Ы Ы В В А А Е Е Т Т С С Я Я П П Е Е Т Т Л Л Е Е Й Й ( ( у у г г р р а а ф ф а а п п е е т т л л я я – – q q ( ( C C , , C C ) ) ) ) . .  Д Д В В А А Р Р Е Е Б Б Р Р А А Н Н А А З З Ы Ы В В А А Ю Ю Т Т С С Я Я С С М М Е Е Ж Ж Н Н Ы Ы М М И И , , Е Е С С Л Л И И О О Н Н И И И И М М Е Е Ю Ю Т Т О О Б Б Щ Щ У У Ю Ю В В Е Е Р Р Ш Ш И И Н Н У У . .
Слайд 6
Ч И С Л О Р Е Б Е Р , И Н Ц И Д Е Н Т Н Ы Х В Е Р Ш И Н Е A , Н А З Ы В А Е Т С Я С Т Е П Е Н Ь Ю Э Т О Й В Е Р Ш И Н Ы И О Б О З Н А Ч А Е Т С Я d e g ( A ) .  d e g ( A ) = 3 ; d e g ( B ) = 3 ; d e g ( C ) = 4 ; d e g ( D ) = 2 ; d e g ( E ) = 0 . ЕСЛИ ВЕРШИНЕ ИНЦИДЕНТНА ПЕТЛЯ, ОНА ЕСЛИ ВЕРШИНЕ ИНЦИДЕНТНА ПЕТЛЯ, ОНА ДАЕТ ВКЛАД В СТЕПЕНЬ, РАВНЫЙ ДВУМ, ДАЕТ ВКЛАД В СТЕПЕНЬ, РАВНЫЙ ДВУМ, ТАК КАК ОБА КОНЦА ПРИХОДЯТ В ЭТУ ТАК КАК ОБА КОНЦА ПРИХОДЯТ В ЭТУ ВЕРШИНУ. ВЕРШИНУ.
Слайд 7
deg(E) = 0  E E – – И И З З О О Л Л И И Р Р О О В В А А Н Н Н Н А А Я Я В В Е Е Р Р Ш Ш И И Н Н А А      d e g ( G ) = 1 d e g ( H ) = 1 d e g ( E ) = 1 d e g ( B ) = 1 d e g ( A ) = 1  G G , , H H , , E E , , B B , , A A - - В В И И С С Я Я Ч Ч И И Е Е В В Е Е Р Р Ш Ш И И Н Н Ы Ы
Слайд 8
В Г Р А Ф Е G ( V , X ) С У М М А С Т Е П Е Н Е Й В С Е Х Е Г О В Е Р Ш И Н – Ч И С Л О Ч Е Т Н О Е , Р А В Н О Е У Д В О Е Н Н О М У Ч И С Л У Р Е Б Е Р Г Р А Ф А :  Ч И С Л О Н Е Ч Е Т Н Ы Х В Е Р Ш И Н Л Ю Б О Г О Г Р А Ф А – Ч Е Т Н О .  Н Е В О З М О Ж Н О Н А Ч Е Р Т И Т Ь Г Р А Ф С Н Е Ч Е Т Н Ы М Ч И С Л О М Н Е Ч Е Т Н Ы Х В Е Р Ш И Н .  В Е Р Ш И Н А Н А З Ы В А Е Т С Я Ч Е Т Н О Й ( Н Е Ч Е Т Н О Й ) , Е С Л И Е Е С Т Е П Е Н Ь – Ч Е Т Н О Е ( Н Е Ч Е Т Н О Е ) Ч И С Л О .
Слайд 9
ГРАФ НАЗЫВАЕТСЯ ПОЛНЫМ , ЕСЛИ ЛЮБЫЕ ДВЕ ЕГО РАЗЛИЧНЫЕ ВЕРШИНЫ СОЕДИНЕНЫ ОДНИМ И ТОЛЬКО ОДНИМ РЕБРОМ. ДОПОЛНЕНИЕМ ГРАФА НАЗЫВАЕТСЯ ГРАФ С ТЕМИ ЖЕ ВЕРШИНАМИ И ИМЕЮЩИЙ ТЕ И ТОЛЬКО ТЕ РЕБРА, КОТОРЫЕ НЕОБХОДИМО ДОБАВИТЬ К ИСХОДНОМУ ГРАФУ, ЧТОБЫ ОН СТАЛ ПОЛНЫМ. ДОПОЛНЕНИЕ
Слайд 10
ДУГИ ДУГИ НАЧАЛО ДУГИ НАЧАЛО ДУГИ ( ( A,B) A,B) КОНЕЦ ДУГИ КОНЕЦ ДУГИ ( ( A,B) A,B)  С Т Е П Е Н Ь Ю В Х О Д А ( В Ы Х О Д А ) В Е Р Ш И Н Ы О Р Г Р А Ф А Н А З Ы В А Е Т С Я Ч И С Л О Р Е Б Е Р , Д Л Я К О Т О Р Ы Х Э Т А В Е Р Ш И Н А Я В Л Я Е Т С Я К О Н Ц О М ( Н А Ч А Л О М ) .  С С Т Т Е Е П П Е Е Н Н И И В В Х Х О О Д Д А А В В Е Е Р Р Ш Ш И И Н Н Г Г Р Р А А Ф Ф А А ( ( с с м м . . р р и и с с . . ) ) : :  С С Т Т Е Е П П Е Е Н Н И И В В Ы Ы Х Х О О Д Д А А В В Е Е Р Р Ш Ш И И Н Н : : ОРГРАФ ОРГРАФ ОРИЕНТИРОВАННЫЙ ГРАФ (ОРГРАФ) — ГРАФ, РЁБРАМ КОТОРОГО ПРИСВОЕНО НАПРАВЛЕНИЕ. НАПРАВЛЕННЫЕ РЁБРА ИМЕНУЮТСЯ ДУГАМИ.
Слайд 11
Последовательность ребер неориентированного графа, в которой вторая вершина предыдущего ребра совпадает с первой вершиной следующего, называется маршрутом . Число ребер маршрута называется длиной маршрута.  H H C C D D F F D D – – М М А А Р Р Ш Ш Р Р У У Т Т Д Д Л Л И И Н Н О О Й Й 4 4 . .
Слайд 12
Если начальная вершина маршрута совпадает с конечной, то такой маршрут называется замкнутым или циклом . Если ребро встретилось только один раз, то маршрут называется цепью .    ( ( t t , , s s , , p p , , r r ) ) – – 4 4 - - Ц Ц И И К К Л Л ( ( t t , , s s , , u u , , r r , , t t , , s s , , p p , , r r ) ) – – 8 8 - - Ц Ц И И К К Л Л п п е е т т л л я я ( ( q q ) ) – – 1 1 - - Ц Ц И И К К Л Л  ( ( t t , , s s , , p p ) ) – – 3 3 - - Ц Ц Е Е П П Ь Ь
Слайд 13
совпадает с началом следующего и все ребра единственны.  Ц И К Л В О Р Г Р А Ф Е – П У Т Ь , У К О Т О Р О Г О С О В П А Д А Ю Т Н А Ч А Л О И К О Н Е Ц .    ( ( u u , , s s , , r r , , t t ) ) – – 4 4 - - п п у у т т ь ь ( ( r r , , u u ) ) – – 2 2 - - п п у у т т ь ь ( ( s s , , r r , , t t ) ) и и ( ( u u , , s s , , r r ) ) – – 3 3 - - ц ц и и к к л л ы ы Путь – упорядоченная последовательность ребер ориентированного графа, в которой конец предыдущего ребра
Слайд 14
ЦЕПЬ, ПУТЬ И ЦИКЛ В ГРАФЕ НАЗЫВАЮТСЯ ПРОСТЫМИ , ЕСЛИ ОНИ ПРОХОДЯТ ЧЕРЕЗ ЛЮБУЮ ИЗ ВЕРШИН НЕ БОЛЕЕ ОДНОГО РАЗА. НЕОРИЕНТИРОВАННЫЙ ГРАФ НАЗЫВАЕТСЯ СВЯЗНЫМ , ЕСЛИ МЕЖДУ ЛЮБЫМИ ДВУМЯ ЕГО ВЕРШИНАМИ ЕСТЬ МАРШРУТ.  Д Л Я Т О Г О , Ч Т О Б Ы С В Я З Н Ы Й Г Р А Ф Я В Л Я Л С Я П Р О С Т Ы М Ц И К Л О М , Н Е О Б Х О Д И М О И Д О С Т А Т О Ч Н О , Ч Т О Б Ы К А Ж Д А Я Е Г О В Е Р Ш И Н А И М Е Л А С Т Е П Е Н Ь , Р А В Н У Ю 2 .
Слайд 15
ГРАФ G НАЗЫВАЕТСЯ ПЛАНАРНЫМ (ПЛОСКИМ), ЕСЛИ СУЩЕСТВУЕТ ТАКОЙ ГРАФ G ' , В ИЗОБРАЖЕНИИ КОТОРОГО НА ПЛОСКОСТИ РЕБРА ПЕРЕСЕКАЮТСЯ ТОЛЬКО В ВЕРШИНАХ. ПЛАНАРНЫЕ ГРАФЫ ПЛАНАРНЫЕ ГРАФЫ
Слайд 16
ЭЙЛЕРОВЫМ ПУТЕМ (ЦИКЛОМ) ГРАФА НАЗЫВАЕТСЯ ПУТЬ (ЦИКЛ), КОТОРЫЙ СОДЕРЖИТ ВСЕ РЕБРА ГРАФА ТОЛЬКО ОДИН РАЗ. ГРАФ, ОБЛАДАЮЩИЙ ЭЙЛЕРОВЫМ ЦИКЛОМ, НАЗЫВАЕТСЯ ЭЙЛЕРОВЫМ .  Г Р А Ф Я В Л Я Е Т С Я Э Й Л Е Р О В Ы М Т О Г Д А И Т О Л Ь К О Т О Г Д А , К О Г Д А О Н – С В Я З Н Ы Й Г Р А Ф , И М Е Ю Щ И Й В С Е Ч Е Т Н Ы Е В Е Р Ш И Н Ы .
Слайд 17
ГАМИЛЬТОНОВЫМ ПУТЕМ(ЦИКЛОМ) ГРАФА НАЗЫВАЕТСЯ ПУТЬ(ЦИКЛ), ПРОХОДЯЩИЙ ЧЕРЕЗ КАЖДУЮ ЕГО ВЕРШИНУ ТОЛЬКО ОДИН РАЗ. ГРАФ, СОДЕРЖАЩИЙ ГАМИЛЬТОНОВ ЦИКЛ, НАЗЫВАЕТСЯ ГАМИЛЬТОНОВЫМ .  ( ( C C , , D D , , A A , , B B , , E E ) ) – – г г а а м м и и л л ь ь т т о о н н о о в в п п у у т т ь ь
Слайд 18
МАТРИЦЕЙ ИНЦИДЕНТНОСТИ ГРАФА G НАЗЫВАЮТ ТАБЛИЦУ B , СОСТОЯЩУЮ ИЗ n СТРОК(ВЕРШИНЫ) И m СТОЛБЦОВ(РЕБРА), В КОТОРОЙ:   b i j = 1 , Е С Л И В Е Р Ш И Н А V j И Н Ц И Д Е Н Т Н А Р Е Б Р У X j b i j = 0 , Е С Л И В Е Р Ш И Н А V i И Н Ц И Д Е Н Т Н А Р Е Б Р У X i • ДЛЯ ОРИЕНТИРОВАННОГО ГРАФА: • ДЛЯ НЕОРИЕНТИРОВАННОГО ГРАФА:    b i j = 1 , Е С Л И В Е Р Ш И Н А V i Я В Л Я Е Т С Я Н А Ч А Л О М Д У Г И X j b i j = 1 , Е С Л И В Е Р Ш И Н А V j Н Е И Н Ц И Д Е Н Т Н А Д У Г Е X j b i j = - 1 , Е С Л И В Е Р Ш И Н А V i Я В Л Я Е Т С Я К О Н Ц О М Д У Г И X j
Слайд 19
М А Т Р И Ц Е Й С М Е Ж Н О С Т И Г Р А Ф А G ( V , X ) Б Е З К Р А Т Н Ы Х Р Е Б Е Р Н А З Ы В А Ю Т К В А Д Р А Т Н У Ю М А Т Р И Ц У A П О Р Я Д К А n , В К О Т О Р О Й : a ij = 1 , ЕСЛИ ( V i , V j )  X a ij = 0 , ЕСЛИ ( V i , V j )  X
Слайд 20
СЛЕДУЮЩИЙ ОРГРАФ ЗАДАЕТСЯ ТАБЛИЦЕЙ ИНЦИДЕНТНОСТИ:
Слайд 21
СЛЕДУЮЩИЙ ГРАФ ЗАДАЕТСЯ ТАБЛИЦЕЙ ИНЦИДЕНТНОСТИ:

Другие презентации по математике



  • Яндекс.Метрика
  • Рейтинг@Mail.ru