Графтар теорияһы

Графтар теорияһы
Өйрәнеү объекты	граф
Асыусы йәки уйлап табыусы	Леонард Эйлер
Вики-проект	Проект:Математика[d]
ACM коды (2012)	10003633
Графтар теорияһы Викимилектә

Алты түбәһе һәм ете ҡабырғаһы булған граф

Графтар теорияһы — дискретлы математиканың графтар үҙенсәлектәрен өйрәнеүсе бүлеге. Дөйөм мәғәнәлә граф ҡабырғалар менән тоташтырылған түбәләр (төйөндәр) күмәклегенән ғибәрәт. Иң теүәл билдәләмә буйынса, граф тип $G=(V,E)$ парҙары күмәклеге атала, бында $V$ теләһә ниндәй иҫәпләү күмәклегенең аҫкүмәклеге, ә $E$ — $V\times V$-тың аҫкүмәклеге.

Графтар теорияһы, мәҫәлән геоинформацион системаларҙа (ГИС) ҡулланыла. Булған йәки яңынан проектланыусы өйҙәр, ҡорлмалар, кварталдар һәм башҡалар түбәләр, ә уларҙы тоташтырыусы юлдар, инженер селтәрҙәре, электр тапшырыу линиялары һәм башҡалар — ҡабырғалар итеп ҡарала. Бындай графта башҡарылған төрлө иҫәпләүҙәрҙе ҡулланыу, мәҫәлән, иң ҡыҫҡа урап үтеү юлын йәки иң яҡын аҙыҡ-түлек магазинын табырға, оптималь маршрут планлаштырырға булышлыҡ итә.

Графтар теорияһының күп һанда сиселмәгән проблемалары һәм әлегә иҫбатланмаған гипотезалары бар.

Графтар теорияһы барлыҡҡа килеү тарихы

Леонард Эйлерҙы графтар теорияһына нигеҙ һалыусы тип һанайҙар. 1736 йылда үҙенең хаттарының береһендә ул Кёнигсбергтың ете күпере проблемаһын әйтеп бирә һәм сиселешен тәҡдим итә, аҙаҡ был мәсьәлә графтар теорияһының классик мәсьәләләренең береһе булып китә. «Граф» терминын беренсе булып 1878 йылда билдәле инглиз математигы Джеймс Джозеф Сильвестр (1814—1897) үҙенең «Nature» мәҡәләһендә ҡуллана.

Графтар теорияһы терминологияһы

Графтар теорияһы терминдары һүҙлеге (терминологияһы) әлеге көндә ҡәтғи билдәләнмәгән. Атап әйткәндә, Гудман, Хидетниеми, 1981 монографияһында әйтелгән: «Программалау донъяһында ике „граф“ йәки „селтәр“ терминдарының ҡайһыһын һайлау тураһында берҙәм фекер юҡ. Беҙ „селтәр“ терминын һайланыҡ, сөнки ул, күренеүенсә, ғәмәли өлкәләрҙә йышыраҡ осрай». «Түбә/нөктә» терминдары менән дә шундай уҡ хәл".

Граф төрҙәре:

• Йүнәлешһеҙ граф (неограф)
• Йүнәлешле граф (орграф)

Графтарҙы яҫылыҡта һүрәтләү

Графтарҙы яҫылыҡта һүрәтләгәндә йышыраҡ шундай тамғалауҙар системаһы ҡулланыла: графтың түбәһе нөктә менән йәки, түбәнең мәғәнәһе асыҡланғанда, тура дүртмөйөштәр, овалдар һәм башҡалар менән һүрәтләнә, уларҙың эсендә түбәнең (алгоритмдарҙың блок-схемалары графтарының) мәғәнәһе асыла. Әгәр түбәләр араһында ҡабырға булһа, ул саҡта ярашлы нөктәләр (фигуралар) һыҙыҡ йәки дуға менән тоташтырылалар. Йүнәлешле граф осрағында дуғалар уҡтар менән алмаштырылалар, йәки ҡабырғаның йүнәлешле булыуын асыҡ күрһәтәләр. Ҡайһы берҙә ҡабырға янына уның мәғәнәһен асыусы аңлатма яҙыу урынлаштыралар, мәҫәлән, сикле автоматтарҙың күсеү графтарында. Планар һәм планар булмаған графтар була. Планар граф — һүрәттә (яҫылыҡта) ҡабырғаларын киҫештермәй һүрәтләргә мөмкин булған граф ул (иң ябайҙары — өсмөйөш йәки бәйле түбәләр пары), шулай булмаһа граф планар түгел. Әгәр графтың циклдары булмаһа (һис юғы, ҡабырғаларын һәм түбәләрен баштағы түбәгә әйләнеп ҡайтырлыҡ бер тапҡыр урап үтеү юлы булған), был осраҡта уны «ағас» тип атау ҡабул ителгән. Графтар теорияһында ағастарҙың мөһим төрҙәре — бинар ағастар, унда һәр түбәнең бер инеүсе ҡабырғаһы һәм теүәл ике сығыусы ҡабырғаһы бар, йәки һуңғыһы булып тора — сығыусы ҡабырғалары юҡ һәм бер тамыр түбәһе бар, уға инеүсе ҡабырға юҡ.

Графтың һүрәтләнешен графтың (абстрактлы структура) үҙе менән бутарға ярамай, сөнки бер графҡа берҙән артыҡ график күҙаллауҙы ярашлы ҡуйырға мөмкин. Һүрәтләү тик түбәләрҙең ҡайһы парҙары ҡабырғалар менән тоташтырылған, ә ҡайһылары юҡ икәнен күрһәтеү бурысын үтәй. Йыш ҡына практикала, ике һүрәтләү бер үк графтың моделдәре буламы тигән һорауға яуап биреүе ҡыйын була (икенсе төрлө әйткәндә, һүрәтләүҙәргә ярашлы графтар изоморфлы буламы). Мәсьәләгә бәйле рәүештә, бер һүрәтләүҙәр икенселәренә ҡарағанда асығыраҡ картина бирә.

Графтар теорияһының ҡайһы бер мәсьәләләре

• Кёнигсбергтың ете күпер проблемаһы — графтар теорияһында тәүге һөҙөмтәләрҙең береһе, Эйлер тарафынан 1736 йылда баҫып сығарылған.
• Дүрт буяу проблемаһы — 1852 йылда аныҡ итеп әйтеп бирелгән, ләкин классик булмаған иҫбатлау 1976 йылда ғына табылған (сферала (яҫылыҡта) карта өсөн 4 буяу етә).
• Коммивояжёр мәсьәләһе — иң билдәле NP-тулы мәсьәләләрҙең береһе.
• Өйөр тураһында мәсьәлә — тағы ла бер NP-тулы мәсьәлә.
• Минималь туплаусы (ҡаплаусы) ағасты табыу.
• Графтар изоморфизмы — бер графтың түбәләрен яңынан нумерлау юлы менән икенсе граф табып буламы.
• Планар граф — графты яҫылыҡта ҡабырғаларын киҫештермәй төҙөп буламы (йәки минималь һандағы ҡатлам, баҫма платала йәки микросхемала элементтарҙы үҙ-ара тоташтырыу йүнәлешен билдәләүҙә ҡулланыла).

Графтар теорияһына шулай уҡ күп кенә бөгөнгө көнгә хәл ителмәгән математик проблемалар инә.

Графтар теорияһының ҡулланылышы

• Химияла (структураларҙы, ҡатмарлы реакциялар эҙмә-эҙлелеген һүрәтләү өсөн, шулай уҡ фазалар ҡағиҙәһе графтар теорияһы мәсьәләһе булараҡ интерпретацияланыуы мөмкин); компьютер химияһы — химияның графтар теорияһына нигеҙләнгән сағыштырмаса яңы өлкәһе. Графтар теорияһы хемоинформатиканың математик нигеҙен тәшкил итә. Графтар теорияһы углеводородтарҙың һәм башҡа органик берләшмәләрҙең изомерҙарының теоретик мөмкин булған һанын теүәл асыҡларға мөмкинлек бирә.
• Информатикала һәм программалауҙа (алгоритмдың граф-схемаһы, автоматтар)
• Элемтә һәм транспорт системаларында. Атап әйткәндә, Интернетта мәғлүмәттәрҙе маршрутлау өсөн.
• Экономикала
• Логистикала
• Схемотехникала (Баҫма платала йәки микросхемала элементтарҙы үҙ-ара тоташтырыу топологияһы графтан йәки гиперграфтан ғибәрәт).

Шулай уҡ ҡарағыҙ

• Словарь терминов теории графов
• Связность графов

Әҙәбиәт

• Дистель Р. Теория графов Пер. с англ. — Новосибирск: Издательство института математики, 2002. — 336 с. ISBN 5-86134-101-X.
• Diestel R. Graph Theory, Electronic Edition. — NY: Springer-Verlag, 2005. — С. 422.
• Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, 1974. 368c.
• Белов В. В., Воробьев Е. М., Шаталов В. Е. Теория графов. — М.: Высш. школа, 1976. — С. 392.
• Берж К. Теория графов и её приложения. М.: ИЛ, 1962. 320c.
• Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. 384с. (Изд.2, испр. М.: УРСС, 2009. 392 с.)
• Зыков А. А. Основы теории графов. — М.: «Вузовская книга», 2004. — С. 664. — ISBN 5-9502-0057-8.(М.: Наука, 1987. 383c.)
• Химические приложения топологии и теории графов. Под ред. Р. Кинга. Пер. с англ. М.: Мир, 1987.
• Кирсанов М. Н. Графы в Maple. М.: Физматлит, 2007. 168 c. http://vuz.exponenta.ru/PDF/book/GrMaple.pdf 2009 йыл 19 февраль архивланған. http://eqworld.ipmnet.ru/ru/library/books/Kirsanov2007ru.pdf
• Кристофидес Н.Теория графов. Алгоритмический подход. М.: Мир, 1978. 429c.
• Кормен Т. Х. и др. Часть VI. Алгоритмы для работы с графами // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: Вильямс, 2006. — С. 1296. — ISBN 0-07-013151-1.
• Оре О. Теория графов. — 2-е изд. — М.: Наука, 1980. — С. 336.
• Салий В. Н. Богомолов А. М. Алгебраические основы теории дискретных систем. — М.: Физико-математическая литература, 1997. — ISBN 5-02-015033-9.
• Свами М., Тхуласираман К. Графы, сети и алгоритмы. М: Мир, 1984. 455с. 2007 йыл 20 март архивланған.
• Татт У. Теория графов. Пер. с англ. М.: Мир, 1988. 424 с. 2020 йыл 3 август архивланған.
• Уилсон Р. Введение в теорию графов. Пер с англ. М.: Мир, 1977. 208с.
• Харари Ф. Теория графов. — М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)
• Харари Ф., Палмер Э. Перечисление графов. — Мир, 1977.
• Сергей Мельников Сим и Крэм под «электронным микроскопом» // Наука и жизнь. — 1996. — В. 3. — С. 144-145. В статье идёт речь об игре на графе Сим, придуманной Густавом Симмонсом.

Һылтанмалар

• WikiGrapp — толковый словарь по теории графов
• Алгоритмы и краткие описания программ на C++
• Дискретная математика, алгоритмы, апплеты, визуализация графов 2014 йыл 11 ғинуар архивланған.
• Графы в химии
• Intelligent Graph Visualizer (автоматическое размещение на плоскости, поиск кратчайшего пути, поиск центра и др.)
• Graph Theory Software 2013 йыл 13 март архивланған.
• Visual Graph: программа, предоставляющая пользователю, широкий набор средств и методов для визуализации и поиска информации в графах