Kas ir grafu teorija un kā grafs tiek definēts kā tāds?

1736. gadā, pamatojoties uz Šveices fiziķa matemātiķa Leonharda Eilera (1707-1783) darbu, tika novērots, ka virsotņu secība nosaka ceļš, tomēr, ja minētais ceļš sastāv no dažādām virsotnēm bez atkārtotām malām, to sauc par ceļu vai ceļu eulerian; ja papildus nonākam sākuma punktā, katru malu šķērsojot tikai vienu reizi, tad mums ir Eilera cikls (shēma).

Citāts (APA)

Aleksandrs Barraza | jūl. 2022
Fizikas grāds

No savas puses mēs definējam grafiku kā sakārtotu pāri (GOES) kur v apzīmē visu grafa virsotņu vai mezglu (netukšo) kopu, kamēr A apzīmē visu to malu vai līniju kopu (tā var būt tukša), kas savieno grafa virsotnes. Komplekta elementi A var apzīmēt kā nesakārtotu pāri {v, w}, kur v un w ir elementi (mezgli vai virsotnes) v, tādā veidā tiek teikts, ka v un w ir blakus virsotnes (tās savienojas ar malu).

Grafu teorija izriet no Eilera sniegtās atbildes uz tautas atjautības problēmu, kas domāja, kā šķērsot septiņus tiltus. pievienojās divām Kēnigsbergas kopienas salām (tolaik daļa no Vācijas un pašlaik Kaļiņingradas Krievijā), starp tām un ar cietzemi, neizmantojot divas reizes vienu un to pašu tiltu un ierodoties sākuma punktā (atrodas kontinentālajā daļā), lai kāds tas būtu, nosakot, ka šajā gadījumā galu galā nē varētu.

Septiņu Kēnigsbergas tiltu problēma

Eilers modelēja Kēnigsbergu kā grafiku, kurā katrs punkts (virsotne vai mezgls) apzīmē tiltu un katra līnija (mala) ceļu uz sauszemes:

Kāds ir šīs problēmas risinājums?

nav neviena risinājums kas atbilst izvirzītajiem nosacījumiem, jo, kā parādīja Eilers, virsotnes nav pāra pakāpes, tas ir, pāra līniju skaits neietekmē katru punktu _[3]. Nešķiet, ka mēs varam darīt daudz ar tik vienkārši definētu struktūru, tomēr, kā tas bieži notiek matemātika, Dažreiz lietas nav tādas, kā izskatās. Tādējādi viena no visproduktīvākajām, transversālajām un starpdisciplinārākajām jomām _[4] cilvēku zināšanas, grafu teorija.

Eilera grafiki vai ar Eilera trajektoriju?

Visiem turpmākajiem grafikiem ir Eilera ceļi _[5]. Vai viņiem visiem ir Eilera cikli?

Ņemsim trešo grafiku:

Numurēsim virsotnes:

Tad mēs redzam, ka ceļš, ko nosaka secība {3,4,6,2,1,3,7,6,5,4,2}, ir Eilera ceļš, jo tas iet cauri visam grafikam, neatkārtojot malas, bet tas nav Eilera cikls, jo nesasniedz sākuma punktu. Kas būtu noticis, ja mēs virsotnes numurētu atšķirīgi? Ne daudz, izņemot to, ka tagad ceļu noteiktu cita pēctecība. Kas būtu noticis, ja mēs ietu citādāk nekā mūsu sākotnējā risinājumā piedāvātais? Uz šo jautājumu ir nedaudz sarežģītāk atbildēt, un tas ietver algoritmus, ar kuriem programmatūras inženieri parasti priecājas. programmēšana.

Lai iegūtu stingrāku pierādījumu par to, kas šeit ir atklāts, mums ir jāatsaucas uz šādu rezultātu:

"Esi G savienots grafiks _[6]. Tad jā G pieder ķēde Eilera, katras virsotnes pakāpe ir pāra, savukārt, ja G ir Eilera ceļš, G ir tieši divas nepāra pakāpes virsotnes _[7] (tieši virsotnes, kur ceļš sākas un beidzas)".

Pēc tam mēs varam pārbaudīt, vai mūsu izvēlētajā grafikā tikai virsotnēm 3 un 6 ir nepāra pakāpe (šī notiktu pat tad, ja virsotņu numerācija būtu bijusi atšķirīga), tāpēc minētajam grafam ir ceļš eilerijs _[8]. Pārējiem grafikiem mēs varam rīkoties līdzīgi un pārbaudīt, vai tiem patiešām ir ceļi un Eilera cikli vai citādi, vai mēs varam uzzīmēt šādus grafikus, nepaņemot zīmuli un neatkārtojot līnijas? Atbildi uz šo jautājumu var secināt no tā, kas jau ir izskaidrots līdz šim, tomēr tas ir uzdevums Interesanti smalko motoriku, atjautības un pacietības ziņā, aicinu lasītāju atrast un uzzīmēt grafikus ar 6 vai vairāk virsotnes ar trajektorija Eileriāns.

Vai ir arī citi grafiku veidi? Vai grafu teorijai ir pielietojums “reālajā” pasaulē?

Šie grafiki, kurus esam ļoti īsi pārskatījuši, ir tikai viens no daudzajiem grafiku veidiem, ko mēs atrodam grafu teorijā. Mēs varam atrast arī tādus grafikus kā koki, kas ir ļoti reprezentatīvi kopās, kur to elementus var klasificēt hierarhijās un skaitīšanas aprēķinos un varbūtība_[9], digrāfi, Hamiltona grafiki _[10]utt.

Grafisko modeļu un tīklu attēls programmā Psycho., autors Ruiss, Ana Marija.

Šīs mīklas, ja mēs tās tā vēlamies saukt, ir ļoti pielietojamas mūsdienu pasaulē tik dažādās situācijās kā: bioloģija molekulārā _[11], skaitļošana_[12], telekomunikācijas _[13] un tīkla analīze _[14]. Tad ir vērts jautāt: vai tas nav vismaz ziņkārīgs, ka problēma ir gandrīz banāls beigsies viens no interesantākajiem un pamanāmākajiem matemātikas rezultātiem? Iespējams, ka šim nolūkam bija nepieciešams viena no izcilākajiem cilvēces prātiem.