Teorija grafov na kratko. Problem poti v uteženih usmerjenih grafih

Izobraževalna izdaja

Yuyukin Nikolaj Aleksejevič

LR št. Podpisano za pečat

uč. Ed. jaz.. , .

Voroneška državna tehnična univerza

394026 Voronezh, Moskovsky Ave. 14

IMENIK MAGNETNIH DISKOV

Oddelek višja matematika ter fizikalno in matematično modeliranje

N.A. Yuyukin

DISKRETNA MATEMATIKA 1. del. Elementi teorije grafov

Vadnica

N.A. Yuyukin

DISKRETNA MATEMATIKA 1. del. Elementi teorije grafov

Vadnica

Voronež 2004

UVOD

Ta priročnik lahko pri predmetu "Diskretna matematika" uporabljajo študenti VSTU, ki študirajo na naslednjih specialitetah:

090102 – Računalniška varnost;

090105 – Celovito zagotavljanje informacijske varnosti avtomatiziranih sistemov;

090106 - Informacijska varnost telekomunikacijski sistemi.

Predmet “Diskretna matematika” zagotavlja pridobivanje znanj in spretnosti v skladu z državnim, splošnim izobrazbenim standardom, hkrati pa prispeva k pridobivanju temeljno izobraževanje, oblikovanje pogleda na svet in razvoj logičnega mišljenja.

Teorija grafov je učinkovito orodje za formalizacijo sodobnih inženirskih problemov, povezanih z diskretnimi objekti. Uporablja se pri načrtovanju integriranih vezij in krmilnih vezij, preučevanju avtomatov in logičnih vezij, pri sistemski analizi, avtomatiziranem nadzoru proizvodnje, pri razvoju računalništva in informacijska omrežja, pri načrtovanju vezij in konstrukcijsko-topološkem načrtovanju itd.

IN učbenik orisuje osnove, osnovne metode in algoritme teorije grafov. Tukaj predstavljamo n-grafe in digrafe; izomorfizmi; drevesa; Eulerjevi grafi; ravninski grafi; prevleke in samostojni kompleti; močna povezljivost

V digrafi; analiza grafa Markovljeve verige; algoritmi za iskanje najkrajših poti v grafih; Problem iskanja Hamiltonovega cikla

V graf; problem trgovskega potnika; naštevanje grafov in preslikav; ekstremne naloge; optimizacijske težave; univerzalne naloge; metoda vej in veza; in tudi razvijati praktične spretnosti pri uporabi zgornjih konceptov.

Namen predmeta je razvijati pri študentih teoretično znanje, praktične veščine na področju modeliranja procesov in pojavov v naravoslovju in tehniki

ke, z možnostjo uporabe matematičnih simbolov za izražanje kvantitativnih in kvalitativnih odnosov predmetov, ki jih je treba izvesti uradne dejavnosti na področju informacijske varnosti na visoki strokovni ravni.

Za dosego tega cilja služijo naslednje naloge:

preučevanje najširšega možnega spektra konceptov teorije grafov;

pridobijo veščine reševanja izobraževalnih in praktičnih problemov;

obvladati optimizacijske metode;

razvijajo sposobnosti oblikovanja in odločanja informacijske naloge, modeliranje in analiza informacij z uporabo grafov.

Disciplina »Diskretna matematika« je ena izmed aplikativnih matematičnih disciplin. Temelji na znanju, ki so ga študenti pridobili med študijem disciplin "Algebra" in " Matematična logika in teorija algoritmov." Pri študiju se uporabljajo znanja in veščine, pridobljene pri študiju discipline “Diskretna matematika”. splošno strokovno in posebne discipline.

1. OSNOVNI POJMI TEORIJE GRAFOV.

1.1. Problemi teorije grafov.

Teorija grafov je veja matematike, ki proučuje sisteme povezav med razne predmete, tako kot se to naredi z uporabo koncepta relacije. Vendar pa neodvisna definicija grafa poenostavi predstavitev teorije in jo naredi bolj razumljivo in vizualno.

Prvi problemi teorije grafov so bili povezani z reševanjem zabavnih problemov in ugank.

Prva naloga. Problem königsberških mostov je postavil in rešil Euler leta 1786. Mesto se je nahajalo na bregovih in dveh otokih reke Pregolya. Otoki so bili med seboj in obalami povezani s sedmimi mostovi, kot je prikazano na sliki.

Pojavilo se je vprašanje: ali je mogoče zapustiti hišo in se vrniti nazaj, tako da prečkamo vsak most natanko enkrat?

Druga naloga. Problem treh hiš in treh vodnjakov. Tam so tri hiše in trije vodnjaki.

Od vsake hiše do vsakega vodnjaka je treba narisati pot, da se poti ne križata. Naloga je bila

rešil Pontrjagin in neodvisno od njega Kuratovski v

Tretja naloga. Približno štiri barve. Pobarvaj poljuben zemljevid na ravnini s štirimi barvami, tako da nobeno sosednje območje ni pobarvano z isto barvo.

Številni rezultati iz teorije grafov se uporabljajo za reševanje praktičnih problemov v znanosti in tehnologiji. Tako je sredi 19. stoletja Kirchhoff uporabil teorijo grafov za izračun kompleksnih električnih vezij. Kot matematična disciplina pa se je teorija grafov oblikovala šele v 30. letih 20. stoletja. V tem primeru se grafi obravnavajo kot nekateri abstraktni matematični objekti. Uporabljajo se pri analizi in sintezi vezij in sistemov, pri načrtovanju in upravljanju omrežij, operacijskih raziskavah, programiranju, modeliranju življenja organizma in na drugih področjih.

1.2. Osnovne definicije.

Graf G= (V,E) je zbirka dveh množic - neprazne množice oglišč V in množice neurejenih in urejenih parov oglišč E. V nadaljevanju bomo obravnavali končne grafe, tj. grafi s končno množico vozlišč in končno družino parov. Neurejen par oglišč imenujemo rob, urejen par pa lok.

Običajno je graf predstavljen z diagramom: oglišča so pike (ali krogi), robovi so črte poljubne konfiguracije. Njeno smer na loku dodatno označuje puščica. Upoštevajte, da pri upodabljanju grafa nosilec

cionalni geometrijske lastnosti rebra (dolžina, ukrivljenost), kot tudi relativni položaj oglišča na ravnini.

Točke, ki ne pripadajo nobenemu robu (loku), imenujemo izolirane. Točke, povezane z robom ali lokom, imenujemo sosednje. Rob (lok) in katero koli od njegovih dveh oglišč imenujemo incident.

Pravijo, da rob (u,v) povezuje točki u in v, lok (u,v) pa se začne v točki u in konča v točki v, medtem ko se u imenuje začetek, v pa konec tega loka.

Par oglišč je lahko povezan z dvema ali več robovi (loki v isti smeri). Takšni robovi (loki) se imenujejo večkratni. Lok (ali rob) se lahko začne ali konča na istem oglišču. Tak lok (rob) imenujemo zanka. Graf, ki vsebuje zanke, se imenuje psevdo graf. Graf, ki ima več robov (lokov), imenujemo multigraf.

Graf brez zank ali več robov se imenuje preprost. Preprost graf se imenuje popoln, če za kateri koli par njegovih vozlišč obstaja rob (lok), ki ju povezuje. Popolni graf z n vozlišči je označen s K n. Na primer, to so grafi

Graf, sestavljen iz enega izoliranega vozlišča (K 1), se imenuje trivialen.

Komplement grafa G je graf G, ki ima enaka vozlišča kot graf G in vsebuje tiste robove, ki jih je treba dodati grafu G, da dobimo popoln graf.

Vsakemu nedigrafistu kanonično se ujema usmerjen graf z enakim nizom vozlišč, v katerem je vsak rob nadomeščen z dvema lokoma, ki incidentata na ista vozlišča in imata nasprotni smeri.

1.3. Stopnje oglišč grafa.

Stopnja (valenca) (oznaka d (v) ali deg (v)) oglišča v enostavnega grafa G je število robov ali lokov, ki incidentirajo z danim ogliščem v. Pri izračunu valence oglišč psevdografa je treba vsako zanko prešteti dvakrat.

Če so stopnje vseh oglišč n-grafa enake k, se graf imenuje navaden (enoten) stopinja. Če je stopnja vozlišča 0, potem je izolirano. Če je stopnja oglišča enaka 1, se oglišče imenuje konec (visi, slepo ulico).

Za digraf se imenuje število lokov, ki izhajajo iz oglišča v

Eulerjev izrek: Vsota stopenj oglišč grafa je

dvojno število reber, tj.

d(vi)

Kjer je n število oglišč; m je število

rebra (loki). To trditev dokazuje dejstvo, da se pri izračunu vsote stopenj oglišč vsak rob upošteva dvakrat - za en konec roba in za drugega.

1.4. Izomorfizem grafov.

Graf se imenuje označen (ali preštevilčen), če se njegova oglišča med seboj na nek način razlikujejo.

nalepke (številke). Upošteva se štetje popolnoma podana v strogem pomenu, če je oštevilčenje njegovih oglišč in robov določeno. V tem primeru se grafa G 1 in G 2 imenujeta enaka (oznaka G 1 = G 2), če njuni nizi oglišč in robov sovpadajo. Dva grafa ali psevdografa G 1 = (V 1 ,E 1 ) in G 2 = (V 2 ,E 2 ) imenujemo

se izkažejo za izomorfne, če obstajajo medsebojno enaki

Tako so grafi, ki se razlikujejo le po številčenju vozlišč in robov, izomorfni. Izomorfizem grafa je ekvivalenčna relacija, ker ima lastnosti:

2 (1) .

Teorija grafov je predvsem eno od podpodročij matematike znak ki je geometrijska metoda pri preučevanju predmetov. Za njenega ustanovitelja velja L. Euler.

Uporaba teorije grafov do konca 19. stoletja je bila omejena na reševanje zabavnih problemov in ni pritegnila večje splošne pozornosti. Od 20. stoletja, ko se je teorija grafov pojavila kot samostojna matematična disciplina, je ugotovila, široka uporaba na področjih znanosti, kot so kibernetika, fizika, logistika, programiranje, biologija, elektronika, transportni in komunikacijski sistemi.

Osnovni koncepti teorije grafov

Osnovni je graf. V terminologiji lahko najdete tak koncept kot omrežje, ki je enako grafu. Slednji je neprazno število točk, to je oglišč, in segmentov, to je robov, katerih oba konca ustrezata danemu številu točk. Teorija grafov ne pojasnjuje pomena robov in vozlišč. Na primer mesta in ceste, ki jih povezujejo, kjer so prve oglišča grafa, druge pa robovi. Večja vrednost v teoriji je podana lokom. Če ima rob smer, se imenuje lok; če ima graf usmerjene robove, se imenuje digraf.

V terminologiji teorije se razlikujejo tudi naslednji koncepti:

Podgraf je graf, katerega robovi in ​​oglišča so vsi med oglišči in robovi.

Povezani graf je tisti, v katerem za dve različni točki obstaja veriga, ki ju povezuje.

Utežen povezan graf je tisti, ki ima dano utežno funkcijo.

Drevo je povezan graf brez ciklov.

Vpeto drevo je podgraf, ki je drevo.

Pri upodabljanju grafa na ravnini se uporablja določen sistem zapisov: izbrano oglišče ustreza točki na najpreprostejši površini, in če je med oglišči rob, so ustrezne točke združene z segmentom. Če je graf usmerjen, so ti segmenti nadomeščeni s puščicami.

Vendar slike grafa ne smete primerjati s samim seboj, tj. z abstraktno strukturo, ker je enemu grafu mogoče dati več grafični prikaz. Risba na ravnini je podana zato, da vidimo, kateri pari oglišč so povezani z robovi in ​​kateri ne.

Nekateri problemi teorije grafov vključujejo:

1. Problem najkrajše verige (menjava opreme, umestitev urgenc in telefonskih central).
2. Problem največjega pretoka (urejanje prometa v dinamičnem omrežju, porazdelitev dela, organiziranje zmogljivosti).
3. Problem premazov in embalaže (postavitev kontrolnih prostorov).
4. Barvanje v grafih (postavitev pomnilnika na elektronskih računalnikih).
5. Povezovanje omrežij in grafov (izdelava komunikacijskega omrežja, analiza komunikacijskih omrežij).

Trenutno je nemogoče programirati večino nalog brez poznavanja teorije grafov. Tako je delo z računalnikom lažje in lažje.

Programiranje uporablja številne strukture in univerzalne metode za reševanje problemov in ena izmed njih je teorija grafov. Njegov pomen je težko preceniti. Teorija grafov v programiranju vam omogoča poenostavitev iskanja informacij, optimizacijo programov, pretvorbo in distribucijo podatkov. Zahvaljujoč algoritmom teorije jih je mogoče uporabiti in oceniti pri uporabi za reševanje specifičnih problemov, spremeniti algoritem, ne da bi zmanjšali stopnjo matematične zanesljivosti končne različice programa.

Pomembna lastnina Nadzorni sistem ali model je zbirka dejanj in podatkovnih enot. Te strukture so edini deli programov in informacij, ki jih preoblikujejo. Zato so grafi temeljni konstrukt programerja.

OBČINSKI SAMOSTOJNI IZOBRAŽEVALNI ZAVOD SREDNJA ŠOLA ŠT. 2

Pripravljeno

Legkokonets Vladislav, učenec 10.A razreda

Praktična uporaba Teorije grafov

Nadzornik

L.I. Noskova, učiteljica matematike

Art Bryukhovetskaya

2011

1. Uvod…………………………………………………………………………………….………….3

2. Zgodovina nastanka teorije grafov………………………………………….………..4

3. Osnovne definicije in izreki teorije grafov…………………………….………6

4. Težave, rešene z uporabo grafov……………………………..………………………..8

4.1 Znani problemi………………………………….………………………...8

4.2 Več zanimive naloge………………………………….……………..9

5.Uporaba grafov v različna področjaživljenja ljudi……………………………...11

6. Reševanje težav………………………………………………………………………………………...12

7. Zaključek………………….…………………………………………………………….13

8. Seznam referenc………….………………………………………………………………14

9.Dodatek……………………………………………………………………………………………15

Uvod

Rojen med reševanjem ugank in zabavne igre Teorija grafov je zdaj postala preprosto, dostopno in zmogljivo orodje za reševanje vprašanj, povezanih s številnimi problemi. Grafi so dobesedno vseprisotni. V obliki grafov lahko na primer interpretirate cestne karte in električna vezja, zemljepisne karte in molekule kemične spojine, povezave med ljudmi in skupinami ljudi. V zadnjih štirih desetletjih je teorija grafov postala ena najhitreje razvijajočih se vej matematike. To poganjajo zahteve hitro rastočega področja uporabe. Uporablja se pri načrtovanju integriranih vezij in krmilnih vezij, pri preučevanju avtomatov, logičnih vezij, blokovnih diagramov programov, v ekonomiji in statistiki, kemiji in biologiji, v teoriji razporejanja. zato ustreznost Tema je po eni strani določena s priljubljenostjo grafov in sorodnih raziskovalnih metod, po drugi strani pa ni razvita, celoten sistem njegovo izvajanje.

Reševanje številnih življenjskih problemov zahteva dolge izračune, včasih pa tudi ti izračuni ne prinesejo uspeha. To je tisto raziskovalni problem. Postavlja se vprašanje, ali je za njihovo rešitev mogoče najti preprosto, racionalno, kratko in elegantno rešitev. Ali je reševanje problemov lažje, če uporabljate grafe? To je določilo tema moje raziskave: “Praktična uporaba teorije grafov”

Namen raziskava je uporabljala grafe, da bi se naučila hitrega reševanja praktični problemi.

Raziskovalna hipoteza. Metoda grafov je zelo pomembna in se pogosto uporablja na različnih področjih znanosti in človekove dejavnosti.

Raziskovalni cilji:

1. Preučite literaturo in internetne vire o tej temi.

2. Preveri učinkovitost metode grafov pri reševanju praktičnih nalog.

3. Potegnite zaključek.

Praktični pomen študije je, da bodo rezultati nedvomno vzbudili zanimanje marsikoga. Ali še nihče od vas ni poskusil zgraditi svojega družinskega drevesa? Kako to narediti pravilno? V glavo transportno podjetje Vsekakor moramo rešiti problem donosnejše uporabe transporta pri prevozu blaga iz destinacije v več naselij. Vsak šolar se je srečal z logičnimi težavami s transfuzijo. Izkazalo se je, da jih je mogoče enostavno rešiti z uporabo grafov.

Delo uporablja naslednje metode: opazovanje, iskanje, selekcija, analiza.

Zgodovina teorije grafov

Za utemeljitelja teorije grafov velja matematik Leonhard Euler (1707-1783). Zgodovino te teorije je mogoče izslediti skozi korespondenco velikega znanstvenika. Tukaj je prevod latinskega besedila, ki je vzet iz Eulerjevega pisma italijanskemu matematiku in inženirju Marinoniju, poslanega iz Sankt Peterburga 13. marca 1736.

»Nekoč so mi zastavili problem o otoku v mestu Königsberg, ki ga obdaja reka s sedmimi mostovi čez njo.

[Dodatek Slika 1] Vprašanje je, ali jih lahko nekdo neprekinjeno obide in gre le enkrat čez vsak most. In potem sem bil obveščen, da tega še nikomur ni uspelo, a nihče ni dokazal, da je to nemogoče. To vprašanje, čeprav banalno, se mi je vendarle zdelo vreden pozornosti ker ne geometrija, ne algebra, ne kombinatorika ne zadoščajo za rešitev. Po dolgem razmišljanju sem našel enostavno pravilo, ki temelji na povsem prepričljivem dokazu, s pomočjo katerega je mogoče pri vseh tovrstnih problemih takoj ugotoviti, ali je takšen obvoz mogoče narediti preko poljubnega števila in poljubnega števila mostov, ki se nahajajo ali ne. Koenigsberški mostovi so nameščeni tako, da jih je mogoče prikazati na naslednji sliki [Dodatek Slika 2], kjer A označuje otok, B, C in D pa dele celine, ločene drug od drugega z rečnimi rokavi

O metodi, ki jo je odkril za reševanje tovrstnih problemov, je Euler zapisal:

»Ta rešitev po svoji naravi očitno nima veliko skupnega z matematiko in ne razumem, zakaj bi to rešitev pričakovali od matematika in ne od katere koli druge osebe, saj je ta odločitev podprta samo z razmišljanjem in ni da bi našli to rešitev, obstajajo kakršni koli zakoni, ki so neločljivo povezani z matematiko. Torej, ne vem, kako se izkaže, da bodo vprašanja, ki imajo zelo malo opraviti z matematiko, bolj verjetno rešili matematiki kot drugi.«

Ali je torej mogoče königsberške mostove obiti tako, da greste samo enkrat čez vsakega od teh mostov? Da bi našli odgovor, nadaljujmo Eulerjevo pismo Marinoniju:

"Vprašanje je ugotoviti, ali je mogoče obiti vseh teh sedem mostov in skozi vsakega le enkrat ali ne. Moje pravilo vodi do naslednje rešitve tega vprašanja. Najprej morate pogledati, koliko odsekov ločeni so z vodo - taki, ki nimajo druge poti od enega do drugega kot skozi most B. v tem primeru Obstajajo štirje takšni odseki - A, B, C, D. Naslednja stvar, ki jo je treba razlikovati, je, ali je število mostov, ki vodijo do teh posameznih odsekov, sodo ali liho. Torej v našem primeru do odseka A vodi pet mostov, do preostalih pa po trije mostovi, torej je število mostov, ki vodijo do posameznih odsekov, liho in že to zadostuje za rešitev problema. Ko je to določeno, se prijavimo naslednje pravilo: če bi bilo število mostov, ki vodijo do vsakega posameznega odseka, sodo, potem obvoznica, o kateri govorimo o, bi bilo mogoče, hkrati pa bi bilo mogoče to obvoznico zagnati s katerega koli mesta. Če bi bili dve od teh številk lihi, saj samo eno ne more biti liho, potem bi tudi takrat lahko prišlo do prehoda, kot je predpisano, vendar mora biti samo začetek obvoza zagotovo vzet iz enega od tistih dveh odsekov, do katerih ni vodila . sodo število mostovi. Če bi končno obstajalo več kot dva odseka, do katerih vodi liho število mostov, potem je takšen premik na splošno nemogoč ... če bi lahko sem prinesli druge, resnejše težave, bi ta metoda lahko bila še bolj koristna in bi morala ne smemo zanemariti."

Osnovne definicije in izreki teorije grafov

Teorija grafov je matematična disciplina, ki je nastala s prizadevanji matematikov, zato njena predstavitev vključuje potrebne stroge definicije. Torej, nadaljujmo z organiziranim uvodom v osnovne koncepte te teorije.

Definicija 1. Graf je zbirka končno število točke, imenovane oglišča grafa, in črte, ki povezujejo nekatera od teh oglišč v parih, imenovane robovi ali loki grafa.

To definicijo lahko formuliramo drugače: graf je neprazna množica točk (vozlišč) in segmentov (robov), katerih oba konca pripadata dani množici točk.

V nadaljevanju bomo označevali oglišča grafa z latinskimi črkami A, B, C, D. Včasih bo graf kot celota označen z enico velika začetnica.

Definicija 2. Točke grafa, ki ne pripadajo nobenemu robu, imenujemo izolirane.

Definicija 3. Graf, ki je sestavljen samo iz izoliranih vozlišč, se imenuje ničelni - štetje .

Zapis: O "– graf z vozlišči, ki nima robov

Definicija 4. Graf, v katerem je vsak par vozlišč povezan z robom, se imenuje popoln.

Oznaka: U" – graf, sestavljen iz n oglišč in robov, ki povezujejo vse možne pare teh oglišč. Tak graf lahko predstavimo kot n-kotnik, v katerem so narisane vse diagonale

Definicija 5. Stopnja oglišča je število robov, ki jim oglišče pripada.

Opredelitev 6. Graf, katerega stopnje vseh k oglišč so enake, se imenuje homogeni stopenjski graf .

Opredelitev 7. Komplement danega grafa je graf, sestavljen iz vseh robov in njihovih koncev, ki jih je treba dodati izvirnemu grafu, da dobimo popoln graf.

Opredelitev 8. Graf, ki ga lahko na ravnini predstavimo tako, da se njegovi robovi sekajo le v ogliščih, imenujemo ravninski.

Opredelitev 9. Mnogokotnik ravninskega grafa, ki ne vsebuje nobenih oglišč ali robov grafa, se imenuje njegova ploskev.

Koncepti ravninskega grafa in obraza grafa se uporabljajo pri reševanju problemov o "pravilnem" barvanju različnih zemljevidov.

Opredelitev 10. Pot od A do X je zaporedje robov, ki vodijo od A do X, tako da imata vsaka dva sosednja roba skupno oglišče in noben rob se ne pojavi več kot enkrat.

Opredelitev 11. Cikel je pot, v kateri se začetna in končna točka ujemata.

Opredelitev 12. Preprost cikel je cikel, ki ne gre več kot enkrat skozi nobeno točko grafa.

Opredelitev 13. Dolžina poti , položen na zanko , imenujemo število robov te poti.

Opredelitev 14. Dve točki A in B v grafu se imenujeta povezani (nepovezani), če obstaja (ne obstaja) pot, ki vodi od A do B.

Opredelitev 15. Graf imenujemo povezan, če sta vsaki dve njegovi točki povezani; če graf vsebuje vsaj en par nepovezanih vozlišč, se graf imenuje nepovezan.

Opredelitev 16. Drevo je povezan graf, ki ne vsebuje ciklov.

Tridimenzionalni model drevesnega grafa je na primer pravo drevo s svojo zapleteno razvejano krošnjo; reka in njeni pritoki prav tako tvorijo drevo, vendar že ravno - na površini zemlje.

Opredelitev 17. Nepovezan graf, ki je v celoti sestavljen iz dreves, se imenuje gozd.

Opredelitev 18. Drevo, v katerem je vseh n oglišč oštevilčenih od 1 do n, imenujemo drevo s preštevilčenimi oglišči.

Tako smo preučili osnovne definicije teorije grafov, brez katerih ne bi bilo mogoče dokazovati izrekov in posledično reševati problemov.

Težave rešene z uporabo grafov

Znani problemi

Problem trgovskega potnika

Problem trgovskega potnika je eden izmed znane težave teorija kombinatorike. Predstavljena je bila leta 1934 in najboljši matematiki so si ob njej zlomili zobe.

Izjava problema je naslednja.
Potujoči trgovec (potujoči trgovec) mora zapustiti prvo mesto, obiskati mesta 2,1,3..n enkrat v neznanem vrstnem redu in se vrniti v prvo mesto. Razdalje med mesti so znane. V kakšnem vrstnem redu je treba iti po mestih, da bo zaprta pot (ogled) trgovskega potnika najkrajša?

Metoda reševanja problema trgovskega potnika

Požrešen algoritem "pojdite v najbližje (ki ga še niste vnesli) mesto."
Ta algoritem se imenuje "požrešen", ker morate v zadnjih korakih močno plačati za pohlep.
Upoštevajte na primer omrežje na sliki [Dodatek Slika 3], ki predstavlja ozek romb. Naj trgovski popotnik začne iz mesta 1. Algoritem »pojdi do najbližjega mesta« ga bo pripeljal do mesta 2, nato 3, nato 4; na zadnjem koraku boste morali plačati za svoj pohlep in se vrniti po dolgi diagonali diamanta. Rezultat ne bo najkrajša, ampak najdaljša tura.

Problem königsberških mostov.

Problem je formuliran na naslednji način.
Mesto Koenigsberg leži na bregovih reke Pregel in dveh otokov. Različne dele mesta je povezovalo sedem mostov. Ob nedeljah so se meščani sprehajali po mestu. Vprašanje: ali se je mogoče sprehoditi tako, da se po odhodu od hiše vrnete nazaj in hodite po vsakem mostu točno enkrat.
Mostovi čez reko Pregel se nahajajo kot na sliki[Dodatek Slika 1].

Razmislite o grafu, ki ustreza diagramu mostu [Dodatek, slika 2].

Za odgovor na vprašanje problema je dovolj ugotoviti, ali je graf Eulerjev. (Sodo število mostov mora segati iz vsaj enega oglišča). Ne moreš hoditi po mestu in enkrat prečkati vse mostove ter se vrniti.

Več zanimivih nalog

1. "Poti".

Problem 1

Kot se spomnite, lovec mrtve dušeČičikov je enkrat obiskal slavne posestnike. Obiskal jih je v naslednjem vrstnem redu: Manilov, Korobochka, Nozdryov, Sobakevich, Plyushkin, Tentetnikov, general Betrishchev, Petukh, Konstanzholgo, polkovnik Koshkarev. Najden je bil diagram, na katerem je Čičikov skiciral medsebojne položaje posesti in podeželskih cest, ki jih povezujejo. Ugotovite, katera posest komu pripada, če se Čičikov po nobeni cesti ni peljal več kot enkrat [Dodatek, slika 4].

rešitev:

Cestni zemljevid kaže, da je Čičikov svojo pot začel s posesti E in končal s posestvom O. Upoštevajte, da le dve cesti vodita do posesti B in C, zato je moral Čičikov potovati po teh cestah. Označimo jih s krepko črto. Identificirani so odseki poti, ki potekajo skozi A: AC in AB. Čičikov ni potoval po cestah AE, AK in AM. Prečrtajmo jih. Označimo s krepko črto ED; Prečrtajmo DK. Prečrtajmo MO in MN; Označimo MF s krepko črto; prečrtaj FO; S krepko črto označimo FH, NK in KO. Poiščimo edino možno za danem stanju pot. In dobimo: posestvo E - pripada Manilovu, D - Korobochki, C - Nozdrevu, A - Sobakeviču, B - Pljuškinu, M - Tentetnikovu, F - Betriščevu, N - Petuhu, K - Konstanzholgu, O - Koškarevu [Dodatek Slika 5].

Problem 2

Slika prikazuje zemljevid območja [Dodatek, slika 6].

Lahko se premikate samo v smeri puščic. Vsako točko lahko obiščete največ enkrat. Na koliko načinov lahko prideš od točke 1 do točke 9? Katera pot je najkrajša in katera najdaljša.

rešitev:

Vezje zaporedno "razslojimo" v drevo, začenši od točke 1 [Dodatek Slika 7]. Vzemimo drevo. številka možne načine zadetki od 1 do 9 so enaki številu "visečih" oglišč drevesa (teh je 14). Očitno je najkrajša pot 1-5-9; najdaljša je 1-2-3-6-5-7-8-9.

2 "Skupine, zmenki"

Problem 1

Udeleženci glasbenega festivala so si po srečanju izmenjali kuverte z naslovi. Dokaži, da:

a) je bilo izročenih sodo število ovojnic;

b) število udeležencev, ki so si kuverte izmenjali liho število, je sodo.

Rešitev: Naj bodo udeleženci festivala A 1, A 2, A 3. . . , In n so oglišča grafa, robovi pa povezujejo pare oglišč, ki predstavljajo fanta, ki si izmenjujeta ovojnice [Dodatek Slika 8]

rešitev:

a) stopnja vsakega vozlišča A i kaže število kuvert, ki jih je udeleženec A i dal svojim prijateljem. Skupno število oddanih ovojnic N je enak vsoti stopinj vseh oglišč grafa N = stopnja. Korak 1 +. A 2 + + . . . + korak. A n -1 + stopnja. In n, N =2p, kjer je p število robov grafa, tj. N – sodo. Posledično je bilo oddanih sodo število kuvert;

b) v enakosti N = stopnja. Korak 1 +. A 2 + + . . . + korak. A n -1 + stopnja. In n mora biti vsota lihih členov soda, to pa je lahko le, če je število lihih členov sodo. To pomeni, da je število sodelujočih, ki so si kuverte izmenjali liho število, sodo.

Problem 2

Nekega dne so se Andrej, Boris, Volodja, Daša in Galja dogovorili, da gredo zvečer v kino. Odločili so se, da bodo izbiro kina in predstave uskladili po telefonu. Odločeno je bilo tudi, da če z nekom ne bo mogoče vzpostaviti stika po telefonu, bo izlet v kino odpovedan. Zvečer se v kinu niso zbrali vsi, zato je bil obisk filma odpovedan. Naslednji dan so začeli ugotavljati, kdo je koga klical. Izkazalo se je, da je Andrej poklical Borisa in Volodjo, Volodja Borisa in Dašo, Boris Andreja in Dašo, Daša Andreja in Volodjo, Galja pa Andreja, Volodjo in Borisa. Komu ni uspelo priti do telefona in zato ni prišel na sestanek?

rešitev:

Narišimo pet pik in jih označimo s črkami A, B, C, D, D. To so prve črke imen. Povežimo pike, ki ustrezajo imenom fantov, ki so klicali.

[Dodatek Slika 9]

Iz slike je jasno, da je vsak od fantov - Andrej, Boris in Volodja - poklical vse ostale. Zato so ti fantje prišli v kino. Toda Galya in Dasha se nista mogli pogovarjati po telefonu (točki G in E nista povezani s črto) in zato v skladu z dogovorom nista prišli v kino.

Uporaba grafov na različnih področjih življenja ljudi

Poleg navedenih primerov se grafi pogosto uporabljajo v gradbeništvu, elektrotehniki, managementu, logistiki, geografiji, strojništvu, sociologiji, programiranju, avtomatizaciji. tehnološki procesi in produkcija, psihologija, oglaševanje. Iz vsega navedenega torej neizpodbitno izhaja praktična vrednost teorije grafov, katere dokaz je bil cilj.

ta študija Na katerem koli področju znanosti in tehnologije srečate grafe. Grafi so čudoviti matematični objekti, s katerimi lahko rešujete matematične, ekonomske in logične probleme, različne uganke in poenostavljate pogoje problemov v fiziki, kemiji, elektroniki in avtomatizaciji. Mnogi matematična dejstva priročno za oblikovanje v grafičnem jeziku. Teorija grafov je del mnogih znanosti. Teorija grafov je ena najlepših in najbolj vizualnih matematične teorije . IN v zadnjem času

Teorija grafov najde vedno več aplikacij v uporabnih vprašanjih. Pojavila se je celo računalniška kemija - razmeroma mlado področje kemije, ki temelji na uporabi teorije grafov. Molekularni grafi , ki se uporabljajo v stereokemiji in strukturni topologiji, kemiji grozdov, polimerov itd., so neusmerjeni grafi, ki prikazujejo strukturo molekul[Dodatek, slika 10] . Oglišča in robovi teh grafov ustrezajo ustreznim atomom in kemične vezi

med njimi. Molekularni grafi in drevesa:[Dodatek, slika 10]

a, b - multigrafi oz. etilen in formaldehid; pravijo izomeri pentana (drevesa 4, 5 so izomorfna drevesu 2).

V stereokemiji organizmov najbolj. Pogosto se uporabljajo molekularna drevesa - glavna drevesa molekularnih grafov, ki vsebujejo samo vsa oglišča, ki ustrezajo atomom C. Kompilacija nizov mol. drevesa in ugotavljanje njihovega izomorfizma omogoča ugotavljanje, da pravijo. strukture in ugotovi skupno število izomerov alkanov, alkenov in alkinov

Proteinska omrežja Proteinska omrežja so skupine fizično medsebojno delujočih proteinov, ki delujejo v celici skupaj in usklajeno ter nadzorujejo medsebojno povezane procese, ki potekajo v telesu.

[priloga sl. 11]. Hierarhični sistemski graf imenovano drevo. Posebnost

drevesa je, da je med katerima koli dvema njegovima ogliščema samo ena pot. Drevo ne vsebuje ciklov ali zank. Običajno drevo predstavlja hierarhični sistem

Za vsak par oglišč drevesa obstaja edinstvena pot, ki ju povezuje. Ta lastnost se uporablja pri iskanju vseh prednikov, na primer po moški liniji, katere koli osebe, katere rodovnik je predstavljen v obliki družinsko drevo, ki je "drevo" v smislu teorije grafov.

Primer mojega družinskega drevesa [Dodatek, slika 12].

Še en primer. Slika prikazuje svetopisemsko družinsko drevo [Dodatek, slika 13].

Reševanje problemov

1.Transportna naloga. Naj bo v mestu Krasnodar baza s surovinami, ki jih je treba razdeliti v mesta Krymsk, Temryuk, Slavyansk-on-Kuban in Timashevsk na enem potovanju, pri tem pa porabiti čim manj časa in goriva ter se vrniti nazaj v Krasnodar .

rešitev:

Najprej naredimo graf vseh možne načine potovanja [Dodatek Slika 14], upoštevajoč realne ceste med temi naselji in razdaljo med njimi. Da bi rešili ta problem, moramo ustvariti še en graf, podoben drevesu [Dodatek Slika 15].

Za udobje rešitve mesta označujemo s številkami: Krasnodar - 1, Krymsk - 2, Temryuk - 3, Slavyansk - 4, Timashevsk - 5.

Rezultat je 24 rešitev, a potrebujemo le najkrajše poti. Od vseh rešitev sta le dve zadovoljivi; to je 350 km.

Podobno je mogoče in mislim, da je potrebno izračunati pravi prevoz iz enega naselje drugim.

Logična težava za transfuzijo. Vedro vsebuje 8 litrov vode, zraven sta dve posodi s prostornino 5 in 3 litre. v petlitrsko ponev morate naliti 4 litre vode in pustiti 4 litre v vedru, tj. enakomerno naliti vodo v vedro in veliko ponev.

rešitev:

Stanje v vsakem trenutku lahko opišemo s tremi številkami [Dodatek, slika 16].

Kot rezultat dobimo dve rešitvi: eno v 7 potezah, drugo v 8 potezah.

Zaključek

Torej, da bi se naučili reševati probleme, morate razumeti, kaj so, kako so strukturirani, iz katerih komponent so sestavljeni, katera so orodja, s katerimi se težave rešujejo.

Pri reševanju praktičnih problemov s teorijo grafov je postalo jasno, da je treba na vsakem koraku, v vsaki fazi njihovega reševanja uporabiti ustvarjalnost.

Že od samega začetka, na prvi stopnji, je v tem, da morate biti sposobni analizirati in kodirati stanje problema. Druga stopnja je shematski zapis, ki je sestavljen iz geometrijske predstavitve grafov, pri tej stopnji pa je element kreativnosti zelo pomemben, saj še zdaleč ni enostavno najti ujemanja med elementi pogoja in ustreznimi elementi pogoja. graf.

Odločanje transportna naloga ali nalogo sestaviti družinsko drevo, sem ugotovila, da je metoda grafov zagotovo zanimiva, lepa in nazorna.

Prepričal sem se, da se grafi pogosto uporabljajo v ekonomiji, managementu in tehnologiji. Teorija grafov se uporablja tudi v programiranju. O tem v tem delu nismo razpravljali, vendar mislim, da je to le vprašanje časa.

To znanstveno delo preučuje matematične grafe, področja njihove uporabe, več problemov je bilo rešenih z uporabo grafov. Poznavanje osnov teorije grafov je potrebno na različnih področjih, povezanih s proizvodnjo in vodenjem poslovanja (na primer urnik izgradnje omrežja, urnik dostave pošte). Poleg tega sem ob delu na znanstvenem delu osvojil delo na računalniku v urejevalnik besedil BESEDA. Tako naloge znanstveno delo dokončana.

Iz vsega navedenega torej neizpodbitno izhaja praktična vrednost teorije grafov, katere dokaz je bil cilj tega dela.

Literatura

Berge K. Teorija grafov in njene aplikacije. -M .: IIL, 1962.

Kemeny J., Snell J., Thompson J. Uvod v končno matematiko. -M .: IIL, 1963.

Ore O. Grafi in njihova uporaba. -M .: Mir, 1965.

Harari F. Teorija grafov. -M .: Mir, 1973.

Zykov A.A. Teorija končnih grafov. -Novosibirsk: Znanost, 1969.

Berezina L.Yu. Grafi in njihova uporaba. -M .: Izobraževanje, 1979. -144 str.

"Soros Educational Journal" št. 11 1996 (članek "Flat graphs");

Gardner M. "Matematični prosti čas", M. "Svet", 1972 (poglavje 35);

Olehnik S. N., Nesterenko Yu., Potapov M. K. "Antique zabavne naloge", M. "Znanost", 1988 (2. del, oddelek 8; dodatek 4);

Aplikacija

Aplikacija

p

riž. 6

riž. 7

riž. 8

Aplikacija

Aplikacija

Aplikacija

p

riž. 14

Aplikacija

Grafi so zabavna, koristna in strašljiva tema. Teorija grafov - "Študentska groza". Algoritmi grafov so neverjetni umi ljudi, ki so jih odkrili.

Kaj je graf? Da bi svojim bralcem odgovoril na to vprašanje, bom temo opisal nekoliko drugače.
Graf je množica predmetov.
V večini problemov so to objekti iste vrste. (Veliko mest, ali veliko hiš, ali veliko ljudi, ali veliko drugih stvari iste vrste)

Če želite rešiti težave s takim nizom, morate vsak predmet iz tega niza označiti kot nekaj. Splošno sprejeto je, da prav to imenujemo vozlišča grafa.

Grafe in osnovne definicije je priročno opisati s slikami, zato morajo biti slike vključene, če želite prebrati to stran.

Kot sem že napisal, je graf niz predmetov. Ti predmeti so običajno iste vrste. Najlažje je dati primer v mestih. Vsak od nas ve, kaj je mesto in kaj je cesta. Vsak od nas ve, da do mesta lahko obstajajo ceste ali pa tudi ne. Na splošno lahko vsak niz predmetov označimo kot graf.

Če govorimo o grafu kot o mestih, potem so lahko ceste zgrajene med mesti ali pa so nekje uničene, nezgrajene ali pa se mesto na splošno nahaja na otoku, ni mostu in so zanimive samo asfaltirane ceste . Kljub temu, da do takega mesta ni ceste, lahko to mesto uvrstimo med številne analizirane objekte, vsi objekti skupaj pa sestavljajo zbirko objektov ali, preprosteje rečeno, graf.

Zagotovo ste že brali učbenike in videli ta zapis G(V,E) ali kaj podobnega. Torej je V nek en objekt iz celotne množice objektov. V našem primeru so množica objektov mesta, zato je V specifično mesto. Ker objekti niso nujno mesta in je beseda predmet lahko zavajajoča, lahko tak predmet iz množice imenujemo točka, točka ali kako drugače, najpogosteje pa ga imenujemo oglišče grafa in ga označujemo s črko V.
V programiranju je to običajno bodisi stolpec ali vrstica dvodimenzionalne matrike, kjer se matrika imenuje bodisi matrika sosednosti ali matrika pojavnosti.

V literaturi, na internetu in na splošno povsod, kjer se kaj piše o grafih, boste naleteli na pojme, kot so loki in robovi. Ta slika prikazuje robove grafa. Tisti. to so trije robovi E1, E2 in E3.

Lok in rob se razlikujeta po tem, da je rob dvosmerna povezava. Hotel je, šel je k sosedu, želel je, vrnil se je od soseda. Če ni čisto jasno, si lahko predstavljate hišo, letališče, leteče letalo in padalca. Padalec lahko gre od doma do letališča, a ko prispe na letališče, se spomni, da je svoje srečno padalo pozabil doma, nato se vrni domov in vzame padalo. — Taka cesta, po kteri se sme hoditi sem in tja, se imenuje rob.
Če je padalec na letalu in skače iz letala, vendar je padalec pozabil nadeti svoje srečno padalo na letalu, ali bo padalec lahko pobral tisto, kar je pozabil? Pot, ki poteka samo v eno smer, se imenuje lok. Običajno pravimo, da rob povezuje dve oglišči, lok pa poteka iz enega oglišča v drugo.

Na tej sliki ima graf samo loke. Loki na grafu so označeni s puščicami, ker je dostopna smer tako jasna. Če je graf sestavljen samo iz takšnih lokov, se tak graf imenuje usmerjen.

Pogosto se boste srečali s konceptoma kontiguitete in incidence. Na sliki sta z rdečo označena dva roba, ki gresta v eno točko. Takšni robovi, tako kot zgoraj opisana oglišča, se imenujejo tudi sosednji.

Marsikaj ni opisanega, lahko pa tale podatek komu pomaga.

TEORIJA GRAFOV, veja diskretne matematike, ki preučuje lastnosti grafov in njihove posplošitve. Graf je par (V, E), kjer je V množica točk, imenovanih vozlišča, E pa je množica parov vozlišč, in če vrstni red, v katerem so navedene točke v paru, ni pomemben, potem je to par vozlišč grafa se imenuje rob, in če je pomemben - lok. Graf, ki vsebuje samo robove, se imenuje neusmerjen graf ali preprosto graf, graf, ki vsebuje samo loke, pa se imenuje usmerjen graf. Na sliki 1 je neusmerjen graf z vozlišči a, b, c, d in robovi (a, b), (b, c), (c, d), (a, d), (a, c), ( b, d), na sliki 2 - usmerjen graf z vozlišči a, b, c, d, e, f in loki (a, b), (b, c), (c, d), (d, e) , (e, f), (f, a).

Zgodovinska skica. Prvi problemi teorije grafov so bili povezani z reševanjem matematične težave zabavne in uganke (glej Kombinatorni problemi klasična). Eden prvih rezultatov teorije grafov je bil kriterij obstoja prehoda vseh robov grafa brez ponovitev, ki ga je pridobil L. Euler (1736) pri reševanju problema königsberških mostov (glej Hamiltonov cikel). Od sredine 19. stoletja se je pojavilo delo, povezano s teorijo grafov, ki vsebuje rezultate, povezane z različnimi aplikacijami matematike. Torej, G. Kirchhoff (1847) za kompilacijo celoten sistem enačb za tokove in napetosti v električnih omrežjih (glej Kirchhoffova pravila) je predlagal, da bi takšno omrežje predstavili kot graf in v tem grafu našli vpeta drevesa, kar vodi k rešitvi problema identifikacije neodvisnih sistemov enačb. Drevo je povezan graf, ki ne vsebuje ciklov (slika 3), vpeto drevo grafa je njegov podgraf, ki je drevo, katerega množica oglišč sovpada z množico oglišč grafa.

A. Cayley (1854) za štetje števila izomerov nasičenih ogljikovodikov prišel do problemov opisovanja in naštevanja dreves z danimi lastnostmi. Izraz graf se je v matematiki uveljavil po izidu monografije nemškega matematika D. Koeniga (1936). Od 2. polovice 20. stoletja so se raziskave teorije grafov močno razširile, predvsem zaradi razvoja diskretne matematike in računalniška tehnologija. Določanje grafa je enakovredno podajanju določene binarne relacije na elementih množice vozlišč V. Zaradi tega in tudi zaradi možnosti vizualne predstavitve grafa v obliki risbe na ravnini se modeli grafov uporabljajo pri konstruiranju algoritmov za reševanje različnih problemov tako v matematiki in naravoslovju kot v humanistiki.

Raziskovalne metode v teoriji grafov. Najprej so izpostavljene kombinatorične metode teoretične analize dane binarne relacije na množici vozlišč. Zelo pomembno (zlasti pri težavah s štetjem) algebraične metode, predvsem metode teorije skupin (zlasti permutacijske skupine). Pri proučevanju polaganja grafa na ravnini se uporabljajo rezultati topološke narave. Naključne grafe preučujemo z metodami teorije verjetnosti.

Posebno vlogo pri preučevanju grafov igra matrične metode. Za graf G je matrika sosednosti A = A(G) = ||a ij || je matrika, v kateri je a ij = 1, če je v grafu G oglišče i povezano z ogliščem j z robom (ali lokom v usmerjenem grafu) in a ij = 0 drugače. V prvem primeru pravimo, da sta točki i in j sosednji, v drugem primeru pa, da nista sosednji. Pot v grafu G je zaporedje ν 0 e 1 ν 1 ...ν n -1 e n ν n, sestavljeno izmenično iz oglišč in robov grafa, v katerem rob e i povezuje oglišča v i -1 in v i, i= l, .. ., n; pravimo, da ta pot povezuje točki v 0 in v n . Pot, v kateri je v 0 = v n, se imenuje cikel. Pot se imenuje veriga (oziroma preprosta veriga), če so vsi njeni robovi (vsa njena oglišča) različni. Za n≥ 1 element na mestu (i, j) v matriki A n enako številu poti dolžine n od točke v i do točke v j. Graf se imenuje povezan, če za kateri koli dve njegovi točki obstaja pot, ki povezuje ti točki. Za graf G s p vozlišči in q robovi, v katerem so oštevilčene tako vozlišča kot robovi, razmislimo o incidenčni matriki B(G), ki je matrika, sestavljena iz ničel in enic z dvema enicama v vsakem stolpcu; v stolpcu, ki ustreza robu, ki povezuje točki i in j, se ena pojavi v vrsticah, oštevilčenih z i in j. Za vsako od oglišč i in j ter za rob, ki ju povezuje, pravimo, da so vpadni; Rang incidenčne matrike B(G) je enak p 1, če je graf G povezan graf.

Mnogi lastne vrednosti Matrika sosednosti grafa ali usmerjenega grafa (pri čemer je vsaka vrednost vzeta tolikokrat, kolikor je njena množina) se imenuje spekter grafa. Spekter grafa z in vozlišči je sestavljen iz n realna števila. Preučevanje spektra grafa nam omogoča, da ugotovimo številne značilnosti njegove strukture.

Problemi teorije grafov. Osrednji del teorije grafov je del, ki preučuje strukturne lastnosti grafov. Ena od značilnosti strukture grafa je zaporedje stopenj njegovih oglišč. Najvišja stopnja neusmerjeni graf imenujemo število robov, ki mu incidentirajo. Grafična delitev sodih naravno število n je njegova predstavitev v obliki vsote p členov n = ∑ p i =1 d i, tako da obstaja graf s p vozlišči, katerih stopnje so enake d 1 ,...,d p . V teoriji grafov je znan učinkovit algoritem, ki omogoča za dano urejeno množico števil (d 1 ,...,d p) ugotoviti, ali obstaja graf s p vozlišči v 1,...,v p za katere zaporedje stopenj (d(v 1) , ..., d(v p)) sovpada s tem nizom. Podrobno je preučena še ena pomembna strukturna lastnost - povezljivost grafa, pa tudi vprašanja, povezana z obstojem poti določene vrste v povezanem grafu.

Poseben del strukturne teorije grafov je faktorizacija grafov, to je razgradnja grafa G = (V, E) na vsoto faktorjev (podgrafov) G 1, ..., G m z nekaj dano premoženje, kjer je G i = (V, E i) in E = E 1 u...uE m - razdelitev množice robov na neprazne disjunktne podmnožice. Najpogostejše vrste faktorizacije: n-faktorizacija, kjer so G i homogeni grafi stopnje n (grafi, katerih stopnje vseh vozlišč so enake in enake n), in drevesna faktorizacija, kjer je vsaka komponenta katerega koli G i, i= 1, ...,m , je drevo. Vsak popoln graf K 2 n, to je graf, v katerem sta kateri koli dve točki sosednji, je 1-faktorizirajoč, vendar ne 2-faktorizirajoč; katerega koli popolnega grafa K 2 n+1 ni mogoče 1-faktorizirati, ampak ga je mogoče predstaviti kot vsoto n faktorjev, ki so cikli. Če pri 1-faktorizaciji govorimo o možnosti razdelitve množice robov na podmnožice, sestavljene iz po parih nesosednjih robov (vsaka od podmnožic je 1-faktor), potem je vsaka razdelitev množice vozlišč grafa na n podmnožic, tako da so vozlišča iz katerih koli dveh različnih podmnožic po paru nesosednja, določa pravilno barvanje grafa v n barvah. Teorija barvanja grafov je nastala in se razvila v povezavi s problemom štirih barv, ki je bil rešen šele na prelomu 1970-80 let.

Naravno povezana z grafom G = (V, E) cela serija grafi, na primer njegovi podgrafi, dodatni graf, robni graf L(G). Za graf G s p oglišči in q robovi je robni graf graf z množico oglišč E, v katerem sta dve oglišči povezani z robom, če in samo če sta ustrezna robova sosednja v G. Kriterij, da dani graf robni graf je, da nima podgrafov, ki pripadajo nizu 9 specifično določenih grafov (s 4, 5 ali 6 vozlišči). Preučevanje posebnih razredov grafov, ki se razlikujejo po določeni značilnosti oz strukturna lastnost, predstavlja eno od smeri teorije grafov.

Če je graf podan binarno razmerje na nizu, potem se pogosto pojavi vprašanje o eni ali drugačni njegovi specifični predstavitvi. Tovrsten problem je problem planarnosti grafa, to je možnost, da ga na ravnini prikažemo z risbo, v kateri ni presečišč robov. Najbolj znan kriterij za planarnost je podan s teoremom Pontryagin-Kuratowskega: graf je planaren, če in samo če ne vsebuje kot podgraf niti popolnega grafa K5 niti dvodelnega grafa K3,3. Graf G = (V, E) se imenuje bipartiten, če je mogoče vozlišča množice V razdeliti na dve podmnožici V 1 in V 2, sestavljeni iz po parih nesosednjih vozlišč, tak graf označimo s K n1, n2 , kjer je n i število oglišč v podmnožici V i, i = 1, 2.

Pomemben del raziskav teorije grafov sestavljajo enumeracijski in ekstremni problemi. Ločen razred ekstremnih problemov so pokrivni problemi. Glavni predmeti študija pri problemih pokrivanja so štiri najpomembnejše grafsko-teoretične konstante: število pokritosti vozlišč α 0 , število pokritosti robov α 1 , število neodvisnosti oglišč β 0 in število neodvisnosti robov ß 1 . Število pokritosti vozlišč grafa G je najmanjše število oglišč v pokrivni množici, to je v množici oglišč, pri katerih je vsak rob grafa G incidenten vsaj enemu oglišču te množice. Število neodvisnosti vozlišč grafa G je največje možno število elementov v neodvisni množici, to je v množici vozlišč, v kateri kateri koli dve točki nista sosednji. Število pokritosti robov in število neodvisnosti robov sta opredeljena podobno. Za vsak povezan graf G s p > 1 vozlišči velja α 0 + ß 0 = α 1 + ß 1 = p, za dvodelni graf pa ß 1 = α 0 . Vrednosti teh konstant so znane samo za nekatere grafe določene vrste. Teorija dominacije je tesno povezana s pokrivanjem problemov. Upošteva prevladujoče množice grafa G = (V, E), to je takšne podmnožice D z V, tako da je katera koli vozlišča iz VD sosednja vsaj eni od vozlišč D. Najpomembnejša konstanta grafa je dominantno število - najmanjše možno število oglišč v njegovem dominantnem številu.

Lit.: König D. Theorie der endlichen und unendlichen Graphen. N. Y., 1950; Berge K. Teorija grafov in njena uporaba. M., 1962; Zykov A. A. Teorija končnih grafov. Novosibirsk, 1969; Harari F. Teorija grafov. M., 1973; Basaker R., Saati T. Končni grafi in mreže. M., 1974; Cameron P., Lint D. Teorija grafov, teorija kodiranja in blokovni diagrami. M., 1980; Ore O. Teorija grafov. 2. izd. M., 1980; Cvetkovič D., Dub M., Zaks H. Spektri grafov. Teorija in uporaba. K., 1984; Sačkov V. N., Tarakanov V. E. Kombinatorika nenegativnih matrik. M., 2000; Kolchin V.F. Naključni grafi. 2. izd. M., 2004; Sačkov V. N. Uvod v kombinatorične metode diskretne matematike. 2. izd. M., 2004.