3. 3. Lista adjunctelor. 14
4. Traverse grafice. 14
4. 1. Căutați în profunzime. 15
4. 2. Căutare în lățime. 17
Referințe. 20
Orice sistem care presupune prezența unor stări discrete sau prezența unor noduri și tranziții între ele poate fi descris printr-un grafic.
Prima lucrare pe teoria graficelor, deținut de celebrul matematician elvețian Euler, a apărut în 1736, Euler a rezolvat puzzle foarte renumite poduri din Königsberg. Termenul "Count" a fost introdus pentru prima oară după 200 de ani (în 1936) de către D. Kenigot. Impetus la dezvoltarea teoriei graficelor obținute la rândul său, din secolele XIX și XX, când a crescut brusc numărul de lucrări în topologie și combinatorică, cu care este legat de rudenie foarte aproape. Graficele au fost utilizate în construcția circuitelor circuitelor electrice și circuitelor moleculare.
Ca o disciplină matematică separată, teoria graficelor a fost introdusă pentru prima dată în lucrarea matematicianului maghiar Koenig în anii 1930.
Recent, graficele și metodele de cercetare asociate pătrund organic aproape la toate nivelurile, aproape toate matematicile moderne. Graficele sunt utilizate în mod eficient în teoria planificare și management, programarea teorie, sociologie, economie, biologie, medicină și geografie. Graficele sunt utilizate pe scară largă în domenii cum ar fi de programare, electronica, în care se ocupă cu probleme probabilistice și combinatoriale, găsirea cea mai scurtă distanță, de potrivire maximă, și altele. Math distractiv și puzzle-uri, de asemenea, fac parte din teoria grafurilor. Teoria graficelor se dezvoltă rapid, găsește toate aplicațiile noi.
1. Concepte de bază
produs cartezian a două seturi A și B este mulțimea de perechi de elemente, astfel încât primul membru al perechii este luată din multimea A, al doilea B: A = B x.
De exemplu, produsul cartezian al seturilor A = și B = este setul A x B = <(0, a), (0, b), (0, c), (1, a), (1, b), (1, c)>.
Un grafic este o pereche G = (V, E), unde V este setul de vârfuri, E este setul de muchii (arce).
Count - un set de număr finit de puncte, numite noduri ale grafului, și perechile de noduri de legătură, unele dintre aceste linii numite muchii sau arce ale graficului.
Vârfurile graficului sunt notate cu literele latine A, B, C, D sau numerice. Uneori, un grafic ca întreg poate fi notat cu o literă mare.
O pereche neregulată de vârfuri este numită margine ordonată de un arc. Adică segmentul dintre vârfuri, având o direcție, se numește arc. Direcția este indicată de o săgeată la sfârșit.
Un segment între nodurile care nu au o direcție este numit margine.
Arcurile sunt ca și drumurile cu sens unic: poți conduce o singură cale. Ribele sunt ca și drumurile cu două sensuri: puteți conduce în ambele direcții.
Prin utilizarea graficelor este posibilă simplificarea sarcinilor stabilite în diverse domenii ale cunoașterii: în automatizare, electronica, fizica, chimie, etc. Cu ajutorul graficelor prezentate scheme de drumuri, conducte, de căldură - și putere .. Graficele ajută la rezolvarea problemelor matematice și economice.
Arkady, Boris. Vladimir, Grigory și Dmitri la întâlnire au schimbat strângerea de mână (fiecare a dat mâna cu fiecare o dată). Câte strângeri de mână au fost făcute?
Punctele A, B, C, D, E, numit nodurile și segmentele de linie care conectează aceste puncte - marginile graficului.
În această problemă, este necesar să se calculeze numărul de margini ale graficului prezentat în figură. Acest număr va fi egal cu numărul de strângere de mână perfectă între cei cinci tineri. Sunt 10 dintre ei.
Un grafic care conține doar arce este denumit orientat.
Orientat este un grafic în care este setul de perechi ordonate de vârfuri ale formei (x, y), unde x este numit începutul, y este sfârșitul arcului. Arcul (x, y) este scris adesea după cum se arată în formularul:
Se crede că arcul conduce de la vârful x la vârful y, iar vârful y este adiacent vârfului x. Un grafic orientat este, de asemenea, numit digraph.
Articole similare
Trimiteți-le prietenilor: