Граф (математика)

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

Граф — абстрактлы математик объект, графтың түбәләренән һәм түбәләр парҙарын тоташтырыусы ҡабырғалар йыйылмаһынан ғибәрәт булған күмәклек. Мәҫәлән, түбәләр күмәклеге итеп ниндәйҙер авиакомпания хеҙмәтләндергән аэропорттар күмәклеген, ә ҡабырғалар күмәклеге итеп был авиакомпанияның ҡалалар араһындағы регуляр рейстарҙы алырға мөмкин.

Төрлө ҡулланыу өлкәләре өсөн графтарҙың төрҙәре йүнәлешлектәре, бәйләнештәр һанына сикләүҙәр һәм түбәләр йәки ҡабырғалар тураһында өҫтәлмә мәғлүмәттәр менән айырылырға мөмкиндәр. Математикала һәм информатикала практик әһәмиәткә эйә булған күп структуралар графатар ярҙамында күрһәтелергә мөмкин. Мәҫәлән, Википедияның төҙөлөшөн түбәләре — мәҡәләләр, ә дуғалары (йүнәлешле ҡабырғалары) — гиперһылтанмалар (тематик карта) булған йүнәлешле граф ярҙамында күрһәтеп була.

Графтар графтар теорияһының төп өйрәнеү объекты булып торалар.

Билдәләмәләр

Графтар теорияһының нығынған терминологияһы юҡ. Төрлө баҫмаларҙа бер үк термин аҫтында төрлө әйберҙәрҙе аңлайҙар. Түбәндә йышыраҡ осраған билдәләмәләр килтерелә.

Граф

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

$V$ (тимәк, $E$ күмәклеге лә, юҡһа ул мультикүмәклек булыр ине) ғәҙәттә сикле күмәклектәр тип иҫәпләнәләр. Сикле графтар өсөн табылған күп һөҙөмтәләр сикһеҙ графтар өсөн дөрөҫ түгел (йәки ни менәндер айырылалар), сөнки сикле тупланмалар өсөн урынлы булған бөтә раҫлауҙар ҙа сикһеҙ күмәклектәр осрағында үтәлмәйҙәр.

Бәйле билдәләмәләр

• Графтың түбәләрен һәм ҡабырғаларын шулай уҡ графтың элементтары тип атайҙар, графтың $|V|$ түбәләр һанын — тәртибе, $|E|$ ҡабырғалары һанын — графтың үлсәме тип атайҙар.

• $u$ һәм $v$ түбәләре $e=\{u,v\}$ ҡабырғаһының ос түбәләре (йәки остары) тип аталалар. Ҡабырға, үҙ сиратында, был түбәләрҙе тоташтыра. Бер үк ҡабырғаның ике ос түбәләре күрше түбәләр тип аталалар.

• Уртаҡ ос түбәләре булған ике ҡабырға эргәләш тип аталалар.

• Ос түбәләре күмәклеге тап килгән ике ҡабырға тапҡырлы тип аталалар.

• Әгәр ҡабырғаның остары тап килһә, йәғни $e=\{v,v\}$ булһа, ҡабырға элмәк тип атала.

• Элмәге һәм тапҡырлы ҡабырғаһы булмаған граф ябай тип атала.

• $V$ түбәһенең $\deg V$ дәрәжәһе тип уға килгән ҡабырғалар һаны атала (был осраҡта элмәктәрҙе ике тапҡыр һанайҙар).

• Әгәр түбә бер ҡабырғаның да осо булмаһа, ул айырылған тип атала; әгәр түбә теүәл бер ҡабырғаның осо булһа, ул аҫылмалы (йәки япраҡ) тип атала.

Йүнәлешле граф

Йүнәлешле граф (ҡыҫҡаса орграф) $G$ — ул $G:=(V,A)$ тәртипкә килтерелгән пар, бында $V$ — буш булмаған түбәләр йәки төйөндәр күмәклеге, һәм $A$ — йүнәлешле ҡабырғалар (дуғалар) тип аталған (тәртипкә килтерелгән) төрлө түбәләр күмәклеге.

Дуға — ул $(v,w)$ тәртипкә килтерелгән түбәләр пары, бында $v$ түбәһен дуғаның башы, ә $w$ — түбәһен аҙағы тип атайҙар. $v\to w$ дуғаһы $v$ түбәһенән $w$ түбәһенә алып бара тип әйтергә була.

Ҡатнаш граф

Ҡатнаш граф $G$ — ул ҡайһы бер ҡабырғалары йүнәлешле, ә айһы берҙәре йүнәлешһеҙ булырға мөмкин булған граф. $G:=(V,E,A)$ тәртипкә килтерелгән тройкаһы менән яҙыла, бында $V$, $E$ һәм $A$ юғарылағы кеүек билдәләнгәндәр.

Йүнәлешле һәм йүнәлешһеҙ графтар ҡатнаш графтарҙың айырым осрағы булып торалар.

Изоморфлы графтар

$G$ графы $H$ графына изоморфлы тип атала, әгәр $G$ графы түбәләре күмәклегенән $H$ графы түбәләре күмәклегенә, түбәндәге үҙсәнлектәргә эйә булған $f$ биекцияһы булһа: әгәр $G$ графында $A$ түбәһенән $B$ түбәһенә барыусы ҡабырға булһа, ул саҡта $H$ графында $f(A)$ түбәһенән $f(B)$ түбәһенә барыусы ҡабырға булырға тейеш, һәм киреһенсә — әгәр $H$ графында $A$ түбәһенән $B$ түбәһенә барыусы ҡабырға булһа, ул саҡта $G$ графында $f^{-1}(A)$ түбәһенән $f^{-1}(B)$ түбәһенә барыусы ҡабырға булырға тейеш. Йүнәлешле граф осрағында был биекция шулай уҡ ҡабырғаның йүнәлешен һаҡларға тейеш. Үлсәмле граф осрағында биекция шулай уҡ ҡабырғаның үлсәмен һаҡларға тейеш.

Башҡа бәйле билдәләмәләр

Графта маршрут тип шундай сикле түбәләр эҙмә-эҙлелеген атайҙар, бында һәр түбә (һуңғыһынан башҡа) эҙмә-эҙлелектәге артабанғы түбә менән ҡабырға ярҙамында тоташтырылған. Ҡабырғалары ҡабатланмаған маршрут сынйыр тип атала. Түбәләре ҡабатланмаған маршрут ябай сынйыр тип атала (ошонан сығып, ябай сынйырҙа ҡабатланған ҡабырғалар юҡ).

Йүнәлешле маршрут (йәки юл) тип орграфта, һәр элементы алдағыға һәм арттағыға ярашлы булған сикле түбәләр һәм дуғалар эҙмә-эҙлелеген атайҙар.

Цикл тип беренсе һәм һуңғы түбәләре тап килгән сынйырҙы атайҙар. Был осраҡта юлдың (йәки циклдың) оҙонлоғо тип уны төҙөүсе ҡабырғалар һанын атайҙар. Әгәр $u$ һәм $v$ түбәләре ниндәйҙер ҡабырғаның остары булһа, ул саҡта, билдәләмәгә ярашлы, $(u,v,u)$ эҙмә-эҙлелеге цикл була. Шундай «яһалма» осраҡтар булдырмаҫ өсөн түбәндәге төшөнсәләрҙе индерәләр.

Юл (йәки цикл), әгәр уның ҡабырғалары ҡабатланмаһа, ябай тип атала; әгәр ул ябай һәм түбәләре ҡабатланмаһа, элементар тип атала.

Юлдарҙың һәм циклдарҙың иң ябай үҙсәнлектәре:

• ике түбәне тоташтырған һәр юлдың шул уҡ түбәләрҙе тоташтырған элементар юлы бар;
• һәр ябай элементар булмаған юлдың элементар циклы бар;
• ниндәйҙер түбә (йәки ҡабырға) аша үтеүсе һәр ябай циклдың шул уҡ түбә (йәки ҡабырға) аша үтеүсе элементар (аҫ-)циклы бар;
• элмәк — элементар цикл.

Граф түбәләре күмәклегендә «$u$-нан $v$-ға юл бар» тип бирелгән Бинар бәйләнеш, эквивалентлылыҡ бәйләнеше була һәм, шунан сығып, ул был күмәклекте графтың бәйлелек компоненттары тип аталған эквивалентлылыҡ кластарына бүлә. Әгәр графтың теүәл бер бәйлелек компоненты булһа, ул саҡта граф бәйле. Бәйлелек компонентында был түбәләрҙе тоташтырыусы минималь юл оҙонлоғо булараҡ алыҫлыҡ төшөнсәһе индерергә була.

$G$ графының һәр максималь бәйле аҫграфы $G$ графының бәйле компонентаһы тип (йәки компонента тип кенә) атала . «Максималь» һүҙе индерелеүгә ҡарата максималь тигәнде аңлата, йәғни күп һанлы элементтары булған бәйле аҫграфҡа инмәгән.

Графтың ҡабырғаһы, әгәр уны юҡ итеү компоненталар һанын арттырһа, күпер тип атала.

Графтарҙың өҫтәлмә характеристикаһы

Граф:

• әгәр теләһә ниндәй $u$,$v$ түбәләре өсөн $u$-нан $v$-ға юл булһа, бәйле тип атала.
• әгәр ул йүнәлешле, һәм теләһә ниндәй түбәһенән теләһә ниндәй икенсе түбәһенә йүнәлешле юл булһа, ныҡ бәйле йәки йүнәлешле бәйле тип атала.
• әгәр ул бәйле һәм күп ҡабатланмаған циклдары булмаһа, ағас тип атала.
• әгәр теләһә ниндәй ике (әгәр элмәк рөхсәт ителмәһә, төрлө) түбәһе ҡабырға менән тоташтырылған булһа, тулы тип атала.
• әгәр уның түбәләрен ике киҫешмәүсе $V_{1}$ һәм $V_{2}$ аҫкүмәклектәренә, һәр ҡабырға $V_{1}$-ҙең түбәһен $V_{2}$-нең түбәһе менән тоташтырырлыҡ итеп бүлеп булһа, ике өлөшлө тип атала.
• әгәр уның түбәләрен $k$ киҫешмәүсе $V_{1}$, $V_{2}$, …, $V_{k}$ аҫкүмәклектәренә, бер үк аҫкүмәклектең түбәләрен тоташтырыусы ҡабырғалар булмаҫлыҡ итеп бүлеп булһа, k-өлөшлө тип атала.
• әгәр бер аҫкүмәклектең һәр түбәһе икенсе аҫкүмәклектең һәр түбәһе менән ҡабырға ярҙамында тоташтырылған булһа, тулы ике өлөшлө тип атала.
• әгәр графты яҫылыҡта ҡабырғалары киҫешмәгән диаграмма менән һүрәтләп булһа, планар тип атала.
• әгәр графтың һәр ҡабырғаһына, ҡабырғаның ауырлығы тип аталған ниндәйҙер һан ярашлы ҡуйылһа, үлсәүле тип атала.
• әгәр графтың өстән ҙурыраҡ булған оҙонлоҡтағы не содержит индукцияланған циклдары булмаһа, хордаль тип атала.

Шулай уҡ була:

• k-буялған
• k-хроматик

Граф төшөнсәһен дөйөмләштереү

Ябай граф бер үлсәмле симплициаль комплекс була.

Тағы ла абстрактлыраҡ, графты $(V,E,\varphi )$ тройкаһы һымаҡ бирергә була, бында $V$ һәм $E$ — ниндәйҙер күмәклектәр (ярашлы рәүештә түбәләр һәм ҡабырғалар), ә $\varphi$ — һәр $e\in E$ ҡабырғаһына $V$-нан (тәртипкә килтерелгән йәки тәртипкә килтерелмәгән) $u$ һәм $v$ түбәләр парын (уның остарын) тап килтереүсе тап килеү функцияһы (йәки инцидентор). Был төшөнсәнең айырым осраҡтары булып торалар:

• йүнәлешле графтар (орграфтар) — әгәр $\varphi (e)$ һәр саҡ тәртипкә килтерелгән түбәләр пары булһа;
• йүнәлешһеҙ графтар — әгәр $\varphi (e)$ һәр саҡ тәртипкә килтерелмәгән түбәләр пары булһа;
• ҡатнаш графтар — йүнәлешле лә, шулай уҡ йүнәлешһеҙ ҙә ҡабырғалары һәм элмәктәре булған граф;
• Эйлер графтары — цикллы Эйлер юлы (Эйлер циклы) булған граф;
• мультиграфтар — тапҡырлы ҡабырғалы, остары бер үк түбәләр пары булған, графтар;
• псевдографтар — ул элмәге булырға мөмкин булған мультиграфтар;
• ябай графтар — элмәктәре һәм тапҡырлы ҡабырғалары булмаған графтар.

Юғарыла килтерелгән билдәләмәгә ҡайһы бер башҡа дөйөмләштереүҙәр тап килмәйҙәр:

• гиперграф — әгәр ҡабырға икенән артыҡ түбәне тоташтыра алһа.
• ультраграф — әгәр $x_{i}$ һәм $u_{j}$ элементтары араһында тап килеүсәнлек бинар бәйләнеше булһа.

Информатикала графты биреү ысулдары

Эргәләшлек матрицаһы

Бағаналары ла, шулай уҡ юлдары ла графтың түбәләре булып тоған таблица. Был матрицаның һәр күҙәнәгенә юл-түбәнән бағана-түбәгә (йәки киреһенсә) бәйләнеш барлығын билдәләүсе һан яҙыла.

Был тығыҙ графтарҙы һүрәтләү өсөн иң уңайлы ысул.

Етешһеҙлеге булып хәтергә түбәләр һанының квадратына тура пропорциональ булған талап тора.

• Ике үлсәмле массив;
• Матрица с пропусками;
• Күренеп тормаған бирелеш (функция ярҙамында).

Тап килешлелек матрицаһы

Юлдары графтың түбәләренә, ә бағаналары графтың бәйләнештәренә (ҡабырғаларына) тап килгән таблица. Матрицаның $i$ юлының $j$ бағанаһы менән киҫелешендәге күҙәүенә яҙыла:

1

әгәр $j$ ҡабырғаһы $i$ түбәһенән «сыҡһа», шул осраҡта;

−1,

әгәр ҡабырға түбәгә «инһә»,

0

бөтә башҡа осраҡтарҙа (йәғни әгәр ҡабырға элмәк булһа йәки түбәгә ҡабырға ярашлы түгел)

Был ысул иң һыйҙырышлы (һаҡлау өсөн үлсәме $|V||E|$) пропорциональ, шуға күрә һирәк ҡулланыла, айырым осраҡтарҙа (мәҫәлән, графта циклдарҙы тиҙ табыу өсөн).

Эргәләшлелек исемлеге

Графтың һәр түбәһенә эргәләш түбәләр теҙеме һаҡланған юл ярашлы булған исемлек. Бындай мәғлүмәттәр структураһы ғәҙәттәге таблица түгел, ә «исемлектәр исемлегенән» ғибәрәт.

Биләгән хәтер үлсәме: $O(|V|+|E|)$.

Был һирәкләнгән графтарҙы биреү өсөн, шулай уҡ, ағымдағы ҡаралған түбәнең «күршеләрен» тиҙ генә табырға кәрәк булған, графты иңгә йәки түбәнгә урап сығыу база алгоритмын тормошҡа ашырғанда, иң уңайлы ысул.

Ҡабырғалар исемлеге

Графтың һәр ҡабырғаһына, был ҡабырғаға ярашлы ике түбә һаҡланған юл ярашлы булған исемлек.

Биләгән хәтер үлсәме: $O(|E|)$.

Был графтарҙы биреү өсөн иң ыҡсым ысул, шуға күрә лә тышҡы һаҡлау йәки мәғлүмәттәр алмашыу өсөн йыш ҡулланыла.

Графтарҙы һүрәтләү телдәре һәм төҙөү программалары

Һүрәтләү телдәре

Машина эшкәртеүенә яраҡлы һәм бер үк ваҡытта кеше үҙләштереү өсөн уңайлы итеп графтарҙы һүрәтләү өсөн бер нисә стандартлаштырылған тел ҡулланыла, улар араһында:

• DOT
• GraphML
• Trivial Graph Format
• GML
• GXL
• XGMML
• DGML

Төҙөү өсөн программалар

Графтарҙы төҙөү өсөн коммерция программалар серияһы эшләнгән, шулай, графтарҙы төҙөү ILOG фирмаһының (2009 йылдан IBM корпорацияһы ҡарамағында) ҡулланма программалар пакеты нигеҙенә һалынған, башҡа программалар араһынан — GoView, Lassalle AddFlow, LEDA (түләүһеҙ редакцияһы бар).

Шулай уҡ графтарҙы төҙөү өсөн ирекле программа igraph һәм ирекле библиотека Boost бар.

Визуаллаштырыу өсөн программалар

Графтарҙы визуаллаштырыу өсөн түбәндәге программалы саралар ҡулланыла:

• Graphviz (Eclipse Public License)
• LION Graph Visualizer.
• Графоанализатор — ҡулланыуға ябай интерфейсы булған урыҫ телле программа (GNU LGPL; тик Windows өсөн генә).
• Gephi — графтарҙы биреү һәм өйрәнеү өсөн график көплөк (GNU GPL, CDDL).
• Библиотека GraphX — .NET өсөн графтарҙы иҫәпләү һәм һүрәтләү өсөн ирекле библиотека, WPF 4.0-ды ҡуллана.
• Библиотека MSAGL — .NET өсөн ирекле библиотека .

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

• Графтарҙы тура ҡабатлау
• Объектлы граф

Әҙәбиәт

• Оре О. Теория графов. — М.: Наука, 1968. — 336 с.
• Уилсон Р. Введение в теорию графов. — М.: Мир, 1977. — 208 с.
• Харари Ф. Теория графов. — М.: Мир, 1973.
• Кормен Т. М. и др. Часть VI. Алгоритмы для работы с графами // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: Вильямс, 2006. — С. 1296. — ISBN 0-07-013151-1.
• Салий В. Н., Богомолов А. М. Алгебраические основы теории дискретных систем. — М.: Физико-математическая литература, 1997. — ISBN 5-02-015033-9.
• Касьянов В. Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003. — С. 1104. — ISBN 5-94157-184-4.
• Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. 384с. (Изд.2, испр. М.: УРСС, 2009. 392 с.)
• Кирсанов М. Н. Графы в Maple. — М.: Физматлит, 2007. — 168 с. — ISBN 978-5-9221-0745-7.
• Графы // Энциклопедический словарь юного математика / Сост. А. П. Савин. — М.: Педагогика, 1985. — С. 86-88. — 352 с.