Fondatorul teoriei grafurilor este Leonard Euler. În 1736, într-una din scrisorile sale, el a formulat și propus o soluție la problema a șapte poduri Koenigsberg, care ulterior a devenit una dintre problemele clasice ale teoriei grafurilor.
1. Într-un grafic care nu are noduri de puteri ciudate, există o ocolire a tuturor muchiilor (fiecare margine fiind trecută exact o singură dată) cu un început la orice vârf al graficului.
2. Într-un grafic care are două și numai două vârfuri cu grade impare, există un ocol cu un început la un vârf cu un grad ciudat și un capăt în celălalt.
3. Într-un grafic cu mai mult de două noduri de grad ciudat, nu există o astfel de ocolire.
Există un alt tip de sarcină legată de deplasarea de-a lungul graficelor. Vorbim despre probleme în care este necesar să găsim o cale care trece prin toate vârfurile și nu mai mult de o dată prin fiecare. Un ciclu care trece prin fiecare vertex și o singură dată este numit linia hamiltoniană (în onoarea lui William Rowan Hamilton, celebrul matematician irlandez al secolului trecut, care a început să studieze astfel de linii). Din păcate, nu sa găsit încă un criteriu general, cu ajutorul căruia ar fi posibil să se decidă dacă graficul dat este Hamiltonian și, dacă da, să găsim pe el toate liniile Hamiltonian.
Formată la mijlocul secolului al XIX-lea. problema celor patru culori arată, de asemenea, ca o sarcină distractivă, dar încearcă să o rezolve au condus la apariția unor studii de grafice care au semnificație teoretică și aplicată. Problema celor patru culori este formulată după cum urmează: "Este posibil ca zona oricărei hărți plate să fie vopsită cu patru culori, astfel încât oricare două zone învecinate să fie vopsite în culori diferite?". Ipoteza că răspunsul a fost afirmativ a fost formulat la mijlocul secolului al XIX-lea. În 1890, sa dovedit o declarație mai slabă, și anume că orice hartă plat este colorată în cinci culori. Prin asocierea oricărui grafic plat cu un grafic plat, obținem o formulă echivalentă a problemei în ceea ce privește graficele: Este adevărat că numărul cromatic al oricărui graf plat este mai mic sau egal cu patru? Numeroasele încercări de a rezolva problema au avut un impact asupra dezvoltării unui număr de direcții în teoria graficelor. În 1976, a fost anunțată o soluție pozitivă a problemei cu utilizarea unui computer.
O altă sarcină topologică veche, care, pentru o perioadă îndelungată de timp, nu a răspuns la decizie și a încântat mințile iubitorilor de puzzle-uri, este cunoscută drept "problema furnizării de electricitate, gaze și apă". În 1917, Henry E.Djudeni ia dat o astfel de formulă. În fiecare dintre cele trei case ilustrate în figură, este necesar să se transporte gaz, lumină și apă.
Grafică teorie. 1
Istoria originii teoriei grafurilor. 1
Regulă a lui Euler. 1
1. Belov Teoria grafurilor, Moscova, "Nauka", 1968.
3. OP Kuznetsov. Adelson-Velsky GM Disciplină matematică pentru un inginer. - M. Energoatomizdat. 1988.
6. Ore O. Teoria grafurilor. - M. Science. 1980.
Articole similare
-
Imperiul imperial imperial - istorie, perioade, apariție, înflorire, declin, dezintegrare, societate
Trimiteți-le prietenilor: