Какъв е начинът на графики?
Думата "графиката" по математика означава картина, където рисува няколко места, някои от които са свързани с линии. На първо място, тя трябва да се каже, че графиките, които ще бъдат обсъдени, за аристократите от миналото нямат нищо общо. Нашите "брои" са в основата на гръцката дума "графика", което означава "писане". Същият корен в "графика" на думите, "Биография".
В математика определение графика е дадена както следва: Брой е ограничен набор от точки, някои от които са свързани с линии. Точките се наричат върхове и свързващи линии - ръбове.
Схема графика, състояща се от "изолирани" пикове, се нарича нула брой. (Фиг.2)
Графиките, които не са изградени всички възможни ъгли, наречени непълни графики. (Фиг.3)
Графики, в които изграждат всички възможни краища се наричат пълни графики. (Фиг.4)
Графика, всеки връх на който е свързан към друг връх от ръб, наречен пълен.
Имайте предвид, че ако пълен граф има п върхове, тогава броят на ръбовете е равно на
Действително, броят на ръбове в пълна графика с п върховете определя като броя на неподреден двойки, съставени от всички N-точките на ръбове на графиката, т.е., броят на комбинациите от п елементи 2 ..:
Резултатът се не е пълна, може да бъде завършена, за да завършите същите върхове, като добави липсващата ръба. Например, Фигура 3 показва част графика с пет върха. На фигура 4, краищата се превръщат графика в пълен графика, показана в различен цвят, множеството от върховете на тези ръбове се нарича комплемента на графиката.
Степени на върха и да разчитат на броя на ръбове.
Броят на ръбовете, напускащи връх на графиката, наречена степента на връх. Vertex като странна степен, наречена странно. и chotnuyu степен - дори.
Ако степента на всички върхове са равни, тогава графиката се нарича хомогенна. По този начин, всеки пълен графика - равномерно.
Фигура 5 показва графика с пет върха. Една степен на възлова точка означен St.A.
Фигурата. St.A = 1 = 2 St.B, St.V = 3 St.G = 2 St.D = 0.
Формулиране на някои закони, свързани с някои графики.
Пълен степен на върха на графиката са еднакви и всеки от тях е по-малко от 1 на броя на върховете на графиката.
Този модел е видно, след разглеждане на всеки пълен граф. Всеки връх е свързан с всеки връх ръб от само себе си, т.е.. Е. Всяка от върховете с п върхове, протича N-1 ръбове, както се изисква.
Сума върховете на градуса е четно число, равно на два пъти броя на ръбове.
Този закон е в сила не само пълен, но и за всяка графика. доказателство:
Всъщност, всеки край на графиката свързва два върха. Така че, ако съберем броя на степените на всички върхове на графа, получаваме два пъти броя на ръбове 2R .. (R - брой на ръбове), че на всеки ръб се брои два пъти, както се изисква
Нечетен брой върхове на графика е дори. доказателство:
Да разгледаме произволно графика G. Да предположим, че в тази графика, броят на върховете на степен 1, е равен на R1; брой възли на степен 2, равни на К2. ; броят на върховете на наш степен, е равна на Кн. Тогава сумата от степените на върховете на графиката може да се запише като
К1 + 2K2 + + ZK3. + NKn.
От друга страна, ако се знае броя на ръбовете на графика R, от двете модели, че сумата от сили на всички върхове на графиката е равна 2R. Тогава можем да запишем уравнението
К1 + 2K2 + + ZK3. + NKn = 2R. (1)
Изолират лявата страна на сума, равна на нечетен брой върхове (К1 + K3 +.):
K1 + 2K2 + ZK3 + 4K4 + 5K5 +. NКодът за + = 2R,
(R1 + R3 + R5 +.) + (2K2 + 2x3 + 4K4 + 4K5 +.) = 2R
Skobka- второ четен брой, като сумата на четни числа. Получената сума (2R) четен брой. Оттук и (К1 + K3 + K5 +.) Е четно число.
Нека сега разгледаме проблема да бъде решен с помощта на графики:
Zadacha.Pervenstvo клас. На шампионата класа тенис на маса 6 участници Андрей, Борис, Виктор, Галина Дмитрий и Елена. Първенството се провежда в кръгова система - един от участниците, които играят всеки един от останалите веднъж. Към днешна дата, някои от игрите са били държани: Андрю играе с Борис, Галина и Елена; Борис, както вече бе споменато, с Андрю и друг с Галина; Victor - Галина Дмитрий и Elena; Галина Андрю и Борис; Дмитрий - с Виктор и Елена - Андрей и Виктор. Колко гейма извършена до момента и колко е останало?
Дискусия. Ние представляваме данните на проблема под формата на диаграма. Участниците ще представят на точките: Андрей - една точка, Борис - буква б, и т.н. Ако двама участници вече са играли помежду си, ние ще се присъедини към тях, изобразяваща точкови сегменти. Получава се от веригата, показана на фигура 1.
Букви А, В, С, D, Е - връх свързване сегменти - краищата на графиката.
Имайте предвид, че точката на пресичане на краищата не са негови възли.
Броят на игри играе до този момент, равен на броя на ръбовете, т.е. 7.
За да се избегне объркване, връх често се описва не точки, както и малки кръгове.
За да намерите броя на игрите, които имат да изпълняват, изграждане на друга графика със същите върхове, но ребрата ще се свържат участниците, които не са играли помежду си (Фигура 2) ръбове в тази графика се обърна 8, след което се оставя да прекарат 8 мача : Андрю - с Виктор и Дмитрий, Борис - С Виктор, Дмитрий и Елена и т.н.
Нека се опитаме да изградим графика за ситуацията, описана в следния проблем:
Zadacha.Kto играе Lyapkin - Tyapkina? В клуба на училище драма решихме да се сложи "The Ревизор" на Гогол. След разгорещен спор. Всичко започна с Lyapkin - Tyapkina.
- Lyapkin - Tyapkin да съм аз! - категорично заяви ген.
- Не, аз ще Lyapkin - Tyapkin, каза Dima.- От ранно детство съм мечтал да олицетворява имиджа на сцената.
- Е, да се откаже от тази роля, ако ще играе главния инспектор - да бъдат щедри Джийн.
- ... И аз - Осип - той не даде неговата щедрост Дима.
- Искам да бъда един от ягоди или кмет, - каза Вова.
- Не, ще им бъда кмет - хор извика Алекс и Борис. - Или Khlestakov -
те добавят едновременно.
Възможно ли е да се разпределят ролите, така че изпълнителите са били щастливи?
Дискусия. Ние представляваме млади актьори най-горния ред на кръгове: А - Алик, B - Борис, The - Вова, D - Джийн, D - Дима, и ролята, която те ще играят - кръгове от втория ред (1 - Lyapkin - Tyapkin 2 - Khlestakov 3 - Osyp, 4 - ягода, 5 - управител). След това всяка от страните ще проведе сегменти, т.е. ребра, с ролите той би искал да играе. Получават графика с десет върхове и десет ръбове (Фигура 3)
За да реши проблема, трябва да изберете пет от десет ръбове без общи върхове. Направете го лесно. Достатъчно е да се отбележи, че върховете 3 и 4 са в единия край на върха А и В, съответно. Това означава, че Осип (горе 3), за да играе Дима, И Zemlyanichku (кой друг?) - Вова. Vershina1 - Lyapkin - Tyapkin - свързан с перки D и Е. Rib 1 - D плаща, защото Дима вече е заето, е 1 - F, Lyapkin - Tyapkina да играе ген. Остава да се свърже върховете А и В при върховете 2 и 5, съответните роли на инспектора и кмет. Това може да стане по два начина: или изберете ръб -5 А и В - 2 или ребро А и Б -2 -5. В първия случай, Алекс ще се играе на кмета и Борис - генерален инспектор, във втория случай, а напротив. Както се вижда от графиката, другата решение на проблема не.
Същият графиката се получава чрез решаване на следните задачи:
Задача. Сърдит съседи. Жителите на пет къщи скарахме един с друг, а не да се срещне при кладенеца, реши да ги (кладенци) се разделят, така че собственикът на всяка къща отиде да "притежава" добре със своята "собствена" път. Дали ще го направи?
Възниква въпросът: е това е необходимо графики в разглобено задачи възможни Това не е да се стигне до решение на чисто логичен начин? Да, можете. Но колоната даде условия на видимост, опростена решение и е установено, прилики задачи, като два гола за един, но това не е толкова малко. А сега си представете проблема, който графики имат 100 или повече възли. И това е тези задачи трябва да реши днешните инженери и икономисти. Там не може без графики.
III. Ойлер графики.
Графика теория - науката е сравнително млад: във времето на Нютон такава наука не съществува, въпреки че те са били в рамките на "семейни дървета" се появи-възлиза на разнообразието от графики. Първата работа по теория на графики принадлежи на Леонард Ойлер, и тя се появява в 1736 в публикациите на Санкт Петербург академия на науките. Започнах тази работа като се вземат предвид следните проблеми:
а) Проблемът на Königsberg мостове. Град Кьонигсберг (сега Калининград) и се намира на брега на река два острова Прегел (гел) Различните части на града са свързани чрез седем мостове, както е показано на фигурата. В неделя жителите на града да се разходят из града. Мога ли да избера един маршрут, за да получите един и само един път за всеки мост и след това обратно до началната точка на пътя?
Преди да се помисли за решаването на този проблем, ще се въведе понятието "Ойлер графики.
Предложения графиката е показано на Фигура 4, кръг на един ход. т.е., без повдигане молива от листа и не преминава през една и съща част на линията повече от веднъж.
Тази цифра, така че просто на външен вид, се оказва, има интересна функция. Ако започнем да се изнесат от върха на Б, а след това ние имаме винаги се случва. А какво ще стане, ако започне да се движи от върха A? Лесно е да се провери, че кръг линия в този случай, ние не може да: ние не винаги ще бъде предадена ребра стигнем до където то вече е невъзможно.
Фиг. 5 е показана графика, която вероятно знаете как се рисува един удар. Това е звезда. Оказва се, че тя изглежда много по-сложно, отколкото на предишния брой, кръг тя може да бъде, като се започне с всеки връх.
Графики, изготвени на фигура 6. Можете също така да се направи един удар на писалката.
Сега се опитват да се направи един удар на графиката, показана на фигура 7
Вие не може да го направи! Защо? Вие не може да се намери на върха? Не! Това не е така. Тази графика обикновено е невъзможно да се направи един удар на писалката.
Начертайте аргументи, които ще ни убедят в това. Помислете за един възел А. три върхове от нея. Ние започваме да се начертае графика с върха. За да мине през всяка от тези краища, ние трябва да дойде от върха, а на един от тях, в някои - времето, необходимо за да се върнете към него във втория и третия изхода време. И тук отново не можем да влиза вече! Така че, ако ние започнем проследяване на върха на А, а след това да го довърша не могат.
Нека сега да приемем, че връх А не е началото. След това в процеса на рисуване, ние трябва да го въведете в единия край, за да преминете към друг и да се върне на третия. И тъй като ние не можем да се измъкнем от нея, а след това на връх А в този случай трябва да бъде краят.
По този начин, връх А трябва да е или в началото или в края на проследяването възел.
Но около три други върхове на нашата графика може да се каже същото. Но първоначалната връх и рисунката може да бъде само един връх и връх край може да бъде само един връх! Така че, парцел на графиката с един удар не е възможно.
Графика, че може да се направи без повдигане молива от хартията, наречен Ойлер (Фигура 6).
Тези графики носят имената на учените Леонард Ойлер.
Zakonomernost1. (Произтичащи от прегледа си ни теорема).
Невъзможно е да се изготви графика с нечетен нечетен брой върхове.
2 модел.
Ако всички върхове на странно, можете да без да вдигате молива от хартията ( "един удар") се извършва само веднъж, за да се направи графиката на всеки ръб. Движението може да започне във всеки връх и да го завърши по същия върха.
3 модел.
Графика като само две нечетни върхове могат да се направят без повдигане молива върху хартията, движението трябва да започне с един от тези нечетни върхове и втория край.
4 модел.
Графика с повече от две нечетни върхове, не е възможно да се направи "един удар".
Фигура (графика), което може да се направи без повдигане молива от хартията, наречена unicursal.
Графика нарича свързан ако всеки два от върховете може да бъде свързан с, т. Е. последователност на ръбове, всеки от които започва след края на предишния.
Графиката е изключен, ако това условие не е изпълнено.
Фигура 7 ясно показва графика изключен. Ако, например, на фигурата между пикове D и Е за провеждане на ръб, след това графиката ще бъдат свързани. (Фиг.8)
Такова ръб в графика теория (след отстраняването на който броят на свързания превръща в несвързано) се нарича мост.
Примери на мостове на фигура 7 могат да служат ребра DE, A3, инж и др., Всеки от които е свързан към връх "изолиран" части на графиката. (Фиг.8)
Disconnected графика се състои от няколко "парчета". Тези "парчета" се наричат компонентите на графиката. Всяка свързан компонент, разбира се, свързан графика. Имайте предвид, че е свързан граф има един свързан компонент.
Теорема.
Графиката е Ойлеров ако и само ако той е свързан и е не повече от два нечетни върхове.
Рисуване графика всеки връх, с изключение на началото и края, ще влезем в същия брой пъти, колкото да излезе от нея. Ето защо, степента на всеки връх трябва да бъде още по-, с изключение на две, което означава, че Ойлер графика има не повече от две нечетни върхове.
Нека сега се върнем към проблема за Кьонигсберг мостове.
Обсъждане на проблема. Означаваме различно сечение на буквите А, В, С, D, и мостове - буквите А, В, С, D, Е, F, G - мостове свързват съответстващи части на града. В тази задача, има само един мост контролно-пропускателни пунктове: преминаване през всеки мост, ние винаги сме една част от себе си в други, както и обратното, движещи се от една част на града до друга, ние със сигурност ще премине по моста. Следователно, изобразен план на града в графика, чиито върхове A, B, C, D (фигура 8) показват отделните части на града, и ръбовете А, В, С, D, Е, F, G - мостове, свързващи съответната секция на , Ребрата често са по-удобни за да представляват по-удобно да не линия сегменти и извити дъги - "".
Ако имаше начин, който отговаря на условието на задачата, ще има непрекъснат затворен байпас тази графика, която минава веднъж на всеки ръб. С други думи, тази графика трябва да се изобразяват с един удар. Но това не е възможно - без значение какво отгоре, ние сме избрали за оригинала, трябва да мине през останалата част на върха, а в същото време всеки "входящи" ръб (моста, на която сме влезли в тази част на града) ще отговаря на "излиза" край мост, който ние и след това се използва, за да излезете от тази част на града): броят на ръбове, които влизат всеки връх е равен на броя на ръбовете от него, т.е. общият брой на ръбове среща на всеки връх трябва да бъде още ... Нашата графика на това условие не е изпълнено, и следователно желания път не съществува.
За тези, които учат английски език
Свързани статии