Графът е краен набор от върхове V и набор от ръбове R, свързващи двойки върхове, G=(V,R). Мощностите на множествата V и R са равни на N и M. Наборът от ребра може да е празен. Примери за върхове са обекти от всякакво естество (населени места, компютърни мрежи). Примери за ръбове са пътища, страни, линии.
Върховете, свързани с ребро, се наричат съседни. Ребрата, които имат общ връх, се наричат още съседни. Ребро и всеки от двата му върха се наричат инцидент. Степента на върха е броят на ръбовете, инцидентни му. Всеки график може да бъде представен на равнината чрез набор от точки, съответстващи на върхове, които са свързани с линии, съответстващи на ръбове.
Пътят на графика е последователност от върхове и ръбове. Маршрутът е затворен (цикличен), ако началният и крайният върхове са еднакви. Маршрутът е прост път, ако всички върхове и ръбове са различни. Един граф е свързан, ако всеки връх е достъпен от всеки друг. Върховете, които нямат инцидентни ръбове, се наричат изолирани.
Матрица на инциденти
Комуникационни списъци
Списък на ребрата
Матрица на съседство на свързан претеглен неориентиран граф на граф
Изграждане на обхващащо свързано дърво с минимално тегло. Алгоритъмът на Kruskal Всички ребра се премахват от графа и се получава обхващащ подграф, където всички върхове са изолирани. Всеки връх е поставен в едноелементно подмножество. Ръбовете са сортирани във възходящ ред на теглата. Ребрата се включват последователно, във възходящ ред на техните тегла, в обхващащото дърво.
Има 4 случая: 1) двата върха на включеното ребро принадлежат към едноелементни подмножества, след което се комбинират в ново, свързано подмножество; 2) един от върховете принадлежи към свързано подмножество, а другият не, тогава включваме втория в подмножеството, към което принадлежи първият; 3) двата върха принадлежат на различни свързани подмножества, тогава комбинираме подмножествата; 4) И двата върха принадлежат към едно и също свързано подмножество, тогава изключваме това ребро.
Пример за изграждане на обхващащо дърво с минимално тегло за графа GG Извършени действия Набор от върхове Графика 1 Изграждане на обхващащ подграф с изолирани и върхове Получаваме 5 единични подмножества: (V 1 ), (V 2 ), (V 3 ), (V 4 ), (V 5 ) 2 Намерете ръба с минимално тегло (R 15) и го добавете към обхващащия подграф. Формирайте свързано подмножество от върхове: (V 1,V 5 ). Запазване на подмножества (V 2), (V 3), (V 4)
Извършени действия Набор от върхове Графика 3 Сред останалите намерете реброто с минимално тегло (R 45) и го добавете към обхващащия подграф Добавете върха към свързаното подмножество: (V 1,V 5, V 4 ). Запазваме подмножествата (V 2 ), (V 3 ) 4 Сред останалите намерете ръба с минимално тегло (R 23) и го добавете към обхващащия подграф. Формирайте ново свързано подмножество от върхове: (V 2,V 3 ) . Запазваме първото свързано подмножество (V 1,V 5, V 4 ).
Извършени действия Набор от върхове Графика 5 Сред останалите намерете ръба с минимално тегло (R 25) и го добавете към обхващащия подграф Комбинирайте подмножествата в едно свързано подмножество (V 1,V 5, V 4,V 2,V 3) ). 6Останалите ръбове не са включени в графиката, защото всички техни върхове вече принадлежат към едно и също свързано множество.
Извършени действия Набор от върхове Графика 7. Получена е графика, която: е обхващащ граф (включени са всички върхове); свързани (всички върхове могат да бъдат свързани чрез маршрути); дърво (без цикли); има минимално тегло. 8 Полученото обхващащо дърво има минимално тегло: R 12 +R 25 +R 15 +R 45 = =80 9 Цикличният номер на графиката G е γ=m-n+1=8-5+1=4, което съответства на броят на ръбовете, които не са в дърво.
Деклариране на променливи Два петелементни масива с цели числа X и Y за съхраняване на координатите на върховете на графиката Целочислен двумерен масив R за съхраняване на теглата на ръбовете на графиката Целочислени променливи i, n и k за броячи на цикли Цяла променлива S за съхраняване на сумата от теглата на ръбовете на дървото с минимално тегло
Генериране на произволни координати на 5 върха на графиката (цикъл върху i). Изчисляване на теглата на ръбовете. Извеждане на матрицата на съседство на претеглен орграф (вложени цикли в n и в k) Извеждане на матрицата на съседство на претеглен неориентиран граф – половината от елементите на първоначалната матрица (начална стойност k=n+1) Основа на програмата
Оборудване:
- компютърен клас, оборудван със съвременна техника, видео проектор, екран;
- компютри с Windows XP, програма Microsoft Office 2003 PowerPoint;
- оборудване за бяла дъска (тема на урока, нови термини). Раздавателен материал.
План на урока.
II. Представяне на нов материал. (10 мин.)
III. Фиксиране на материала. Практическа работа. (15-20 мин.)
IV. Обобщаване на урока (2 мин.)
V. Домашна работа.
I. Организационен момент. Актуализация на знанията.
Здравейте! Нашият урок се нарича "Графики". Ще се запознаем с понятието „Графики“, ще се научим да ги изобразяваме и ще решаваме задачи по тази тема.
II Представяне на нов материал.
Първата работа по теория на графите принадлежи на Леонхард Ойлер (1736 г.), въпреки че терминът "граф" е въведен за първи път през 1936 г. от унгарския математик Денеш Кьониг. Графиките се наричаха схеми, състоящи се от точки и сегменти от прави линии или криви, свързващи тези точки (примери за графики са показани на фигура 1)
С помощта на графики често се опростява решаването на проблеми, формулирани в различни области на знанието: в автоматизацията, електрониката, физиката, химията и др. С помощта на графики се изобразяват диаграми на пътища, газопроводи, топлинни и електрически мрежи . Графиките помагат при решаването на математически и икономически проблеми.
Графа - (от гръцки grapho - пиша) е средство за визуално представяне на елементите на обекта на връзките между тях. Това са прекрасни математически обекти, с тяхна помощ можете да решите много различни, външно различни проблеми.
Графиката е някакъв информационен модел
Графът се състои от върхове или възли, свързани с дъги или сегменти - ръбове. Линията може да бъде насочена, т.е. да има стрелка (дъга), ако не е насочена - ръб. Два върха, свързани с дъга или ръб, се наричат съседни.
Примери за графики (Слайд 4, 5, 6)
Задача 1 (Слайд 7):
Установена е космическа комуникация между деветте планети от Слънчевата система. Редовните ракети летят по следните маршрути:
Земя - Меркурий; Плутон – Венера; Земя – Плутон; Плутон - Меркурий; Меркурий – Венера; Уран - Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер - Марс; Марс – Уран.
Възможно ли е да се лети с обикновени ракети от Земята до Марс?
Решение: Да начертаем схема на условието: планетите ще изобразим с точки, а маршрутите на ракетите с линии.
Сега веднага става ясно, че е невъзможно да се лети от Земята до Марс.
Два върха, свързани с дъга или ръб, се наричат съседни. Всеки ръб или дъга е свързан с число. Числото може да показва разстоянието между населените места, времето на преминаване от един връх на друг и др.
Задача 2 (слайд 9) - решението е на дъската. Маша дойде в зоопарка и иска да види колкото се може повече животни. Кой път да поеме? Жълто, червено, зелено?
Задача 3 (11 слайд) - решението е на дъската. Пет футболни отбора A, B, C, D, E трябва да играят мачове помежду си. Вече играно A с B, C, D; B c A, C, D. колко мача са изиграни досега? Колко остава за игра?
Представяне на графика (Слайд 12)
Графиката може да бъде представена като списък от дъги (AB; 7), графично или с помощта на таблица.
| Дъгови списъци | Графична форма | таблична форма | ||||||||||||||||
| (AB; 7), |  |
|
III. Консолидиране на материалите: учениците са поканени да се разделят на групи и да изпълняват задачи. Работейки в малка група, учениците обсъждат модели въз основа на теоретичните знания, получени в началото на урока. Така се постига повторение и затвърдяване на материала.
Задача 2 (Слайд 13)
IV. Обобщение на урока
Момчета, какви нови думи научихте днес? (Брой, връх на графика, ръбове на графика.)
Какво могат да представляват върховете на една графа? (Градове; обекти, които са; свързани.)
Какво означават ръбовете на графиката (Пътища, движения, посоки)
Дайте пример къде в живота можем да ги срещнем?
Как се показват графиките?
V. Домашна работа. (Слайд 15)
1 слайд
2 слайд
За първи път основите на теорията на графите се появяват в трудовете на Леонхард Ойлер (1707-1783; швейцарски, немски и руски математик), в които той описва решаването на пъзели и математически развлекателни задачи. Теорията на графите започва с решението на Ойлер на проблема за седемте моста на Кьонигсберг.
3 слайд
Отдавна сред жителите на Кьонигсберг е разпространена такава гатанка: как да минеш през всичките мостове (през река Преголя), без да минеш нито един от тях два пъти? Мнозина се опитаха да решат този проблем както теоретично, така и практически по време на разходки. Но никой не е успял да направи това, но никой не е успял да докаже, че е дори теоретично невъзможно. На опростена диаграма части от града (графика) съответстват на мостове с линии (дъги на графиката), а части от града съответстват на точки на свързване на линии (върхове на графиката). В хода на разсъжденията си Ойлер стига до следните изводи: Невъзможно е да се премине през всички мостове, без да се премине през някой от тях два пъти.
4 слайд
Има 4 кръвни групи. Когато се прелива кръв от един човек на друг, не всички групи са съвместими. Но е известно, че същите групи могат да се преливат от човек на човек, т.е. 1 - 1, 2 - 2 и т.н. И също така група 1 може да се прелива на всички останали групи, групи 2 и 3 само на група 4. Задача.
5 слайд
6 слайд
Графики Графиката е информационен модел, представен в графична форма. Графът е набор от върхове (възли), свързани с ръбове. Граф с шест върха и седем ребра. Върховете се наричат съседни, ако са свързани с ребро.
7 слайд
Насочени графи - диграфи Всяко ребро има една посока. Такива ръбове се наричат дъги. Насочена графа
8 слайд
Претеглена графика Това е графика, на чиито ръбове или дъги са присвоени числови стойности (те могат да представляват например разстоянието между градовете или цената на транспорта). Теглото на граф е равно на сумата от теглата на неговите ребра. Таблицата (тя се нарича тегловна матрица) съответства на графиката. 1 2 4 2 3 А Б В Г Д
9 слайд
Задача Изградени са пътища между населените места A, B, C, D, E, F, чиято дължина е показана в таблицата. (Липсата на число в таблицата означава, че няма пряк път между точките). Определете дължината на най-краткия път между точки A и F (приемайки, че можете да се движите само по изградените пътища). 1) 9 2) 10 3) 11 4) 12
10 слайд
1. 2. 3. 4. 5. Дължината на най-късия път A-B-C-E-F е 9 2 4 2 4 7 1 2 4 7 1 3 4 2 4 7 1 3 4 3 2 4 7 1 3 4 3 2
Коробова Анастасия, студент гр. 14-PGS-48D
В наше време е важно да се изучават различни методи, свойства и нестандартни приложения. Ще разгледаме приложението на метода "Графика" в заобикалящата ни действителност.
Думата "графика" в математиката означава картина, на която са начертани няколко точки, някои от които са свързани с линии. На първо място, струва си да се каже, че графовете, които ще бъдат обсъдени, нямат нищо общо с аристократите от миналото. Нашите „графики“ произлизат от гръцката дума „grapho“, което означава „пиша“. Същият корен в думите "графика", "биография".
Първата работа по теория на графите принадлежи на Леонхард Ойлер и се появява през 1736 г. в публикациите на Академията на науките в Санкт Петербург.
Графи отговарят:
по физика - при конструиране на електрически вериги
в химията и биологията - при изучаването на молекулите на техните вериги
в историята - при съставяне на родословни дървета (родословие)
по география – по картографиране
в геометрията - чертежи на многоъгълници, полиедри, пространствени фигури
по икономика - при решаване на проблеми за избор на оптимален път за товарните транспортни потоци (авиолинии, метро, железопътни линии)
Теорията на графите се използва при решаване на задачи от математически олимпиади. Графиките дават видимост на условията на проблема, опростяват решението и разкриват сходството на проблемите.
Сега във всеки клон на науката и технологиите се срещате с графики.
Изтегли:
Преглед:
За да използвате визуализацията на презентации, създайте акаунт в Google (акаунт) и влезте: https://accounts.google.com
Надписи на слайдове:
Презентация по математика Тема: "Графики" Попълнена от ученик от група 14-ПГС-48Д Коробова Анастасия
Графиката е фигура, състояща се от точки и линии, свързващи тези точки. Правите се наричат ръбове на графиката, а точките се наричат върхове. Върховете, от които излизат четен брой ръбове, се наричат четни, а нечетен брой се наричат нечетни. Примери за графики Теория на графите
Леонхард Ойлер (4 април 1707 г., Базел, Швейцария - 7 септември 1783 г., Санкт Петербург, Руска империя) е швейцарски, немски и руски математик, който има значителен принос за развитието на математиката, както и на механиката, физиката, астрономия и редица приложни науки. Ойлер е автор на повече от 800 статии по математически анализ, диференциална геометрия, теория на числата, приблизителни изчисления, небесна механика, математическа физика, оптика, балистика, корабостроене, музикална теория и др.
Фигура (графика), която може да бъде начертана, без да се вдига моливът от хартията, се нарича уникурсална. Модел 1. Граф, който има само два нечетни върха, може да бъде начертан, без да вдигате молива от хартията, докато движението трябва да започне от един от тези нечетни върха и да завърши на втория от тях. (Фиг. A) Модел 2 . Граф с повече от два нечетни върха не може да бъде начертан с „един щрих“ (фиг. B) Графи на Ойлер B A
Модел 3. Ако всички върхове на графиката са равномерни, тогава без да вдигате молива от хартията, като рисувате по всеки ръб само веднъж, начертайте тази графика. Движението може да започне от всеки връх и да завърши в същия връх.
Отдавна сред жителите на Кьонигсберг е разпространена такава гатанка: как да минеш през всичките мостове (през река Преголя), без да минеш нито един от тях два пъти? Мнозина се опитаха да решат този проблем, както теоретично, така и практически, по време на разходки Проблемът с мостовете на Кьонигсберг.
Това е графика, в която някои ръбове могат да бъдат насочени, а други могат да бъдат неориентирани. Смесено броене
Претеглена графика 1 2 4 2 3 A B C D E
Дърво е всяка свързана графа, която няма цикли. Дървета Дървета
Това е (мулти)граф, на чиито ръбове е присвоена посока. Насочените ръбове се наричат още дъги. Насочена графа
Графи отговарят:
Теорията на графите се използва при решаване на задачи от математически олимпиади. Графиките дават видимост на условията на проблема, опростяват решението и разкриват сходството на проблемите. Сега във всеки клон на науката и технологиите се срещате с графики.
Благодаря за вниманието!