1. Un grafic este un sistem al unor obiecte, împreună cu unele perechi ale acestor obiecte, care descriu relația dintre ele. Un grafic neorientat (respectiv, un grafic direcționat sau digraph) G - Sistemul este G = (V, E, T), constând dintr-o multitudine de elemente V =, numite nodurile graficului, o multitudine de elemente E =, numite nervuri și afișare, atribuind fiecărui element o pereche de elemente dezordonate (respectiv comandate) numite capetele muchiei e.
Pentru un grafic nedirecționat, valorile V1 și V2 pot fi arbitrare. Pentru orientare - V1 - începutul căii, V2 - sfârșitul.
formează un set de elemente grafice; se presupune că
Cartografia r determină raportul de incidență al muchiei cu fiecare dintre capetele sale. Pentru graficul G = (V, E, F), folosim și notația mai scurtă G = (V, E) fără a indica incidentele care sunt determinate de context.
Dacă este un parapri v1 - v2 ordonat, atunci marginea e se numește un arc orientat care emite de la vârful v1 și intră în vârf; este numit începutul și sfârșitul arcului e. Dacă este o pereche neordonată, atunci marginea e se spune că este nedirecționată.
La fiecare grafic G se poate asocia un grafic nedirecționat corelat cu aceleași seturi V și E și incidente, dar toate perechile sunt neordonate.
Vârful, care nu intră în contact cu nicio margine, se numește izolat. Un vârf care se incadreaza exact la o margine, iar marginea in sine este numita terminal sau agatat.
O margine cu capete potrivite se numește o buclă.
Două vârfuri care intră pe aceeași margine se numesc noduri adiacente (sau adiacente). Două margini care intră în același vârf sunt considerate a fi învecinate.
Marginile care corespund aceleiași perechi de vârfuri sunt numite multiple sau paralele.
2. Graficele pot fi diferite și nu diferite. De obicei, acest lucru este asociat cu noțiunea de izomorfism grafic.
Se spune că două grafice sunt izomorfe dacă există mapări individuale care păstrează incidența, adică, e Є E1
3. Există mai multe moduri de a specifica grafice:
1) Enumerarea (listă) a marginilor graficelor, cu indicarea capetelor acestora și adăugarea unei liste de vârfuri izolate.
2) incidența graficului Matrice cu vârfuri b și p nervuri - matrice dreptunghiulară cu rânduri b și coloane p, rândurile de care corespund vîrfurile graficului, iar coloanele - coaste și j pentru un element grafic neorientat al matricei este 1 dacă incidentul coaste vershinai, și este egală cu 0 în caz contrar. Pentru un grafic orientat, este începutul arcului = +1, dacă v. - sfârșitul arcului În fiecare coloană a matricei de incidență există două elemente non-zero dacă marginea nu este o buclă. Bucla corespunde unui element egal cu 2.
3) matricea cartier (contiguitate) de noduri cu nodurile b - pătrat matritsarazmernosti L, rândurile și coloanele care corespund vîrfurile grafic, nenegative elementraven numărul de nervuri care se extind de la vârful nodului (nu este egal, în general, cu toate acestea, pentru matricea neorientat grafice cartier - simetrice). Pentru nodurile ne-adiacente, elementul corespunzător al matricei este 0.
4) Pentru claritate, graficul este adesea reprezentat ca un obiect geometric: nodurile corespund diferitelor puncte selectate în spațiu (în plan), nervurile - segmente de curbe care leagă punctele corespunzătoare și care trece prin punctele selectate, altele decât capetele lor.
5. Un grafic este numit subgraf al unui graf al notatiei: daca incidentele graficului G sunt pastrate pentru seturi, atunci, evident, fiecare margine a lui E 'intra in subgraful H impreuna cu capetele sale.
De obicei, sunt luate în considerare numai subgrafe fără noduri izolate sau subgrafe care conțin toate nodurile graficei (și numai o parte a marginilor); astfel de subgrafe sunt complet determinate de setul de muchii lor. În aceste cazuri, putem defini în mod firesc operațiunile set-teoretice pe subgrafe: intersecție, uniune, diferență simetrică (numită și sumă modulo 2 sau pur și simplu o sumă), o completare a întregului grafic.
Un subgraf cuprins de un set de noduri
G, este un subgraf care conține vârfuri de V și toate marginile graficului G care unește perechile de vârfuri de la
Un subgraf alcătuit din toate marginile care intră în contact cu un vârf se numește o stea de vârf
Pentru grafice fără bucle gradul unui vârf # 945; există un număr de margini în steaua Z # 945 ;. Este evident că suma gradelor tuturor vârfurilor unui grafic fără bucle este egală cu dublul numărului de muchii.
Toate subiectele din această secțiune:
N, n) - locurile fără repetiție se numesc n-permutări sau permutări ale elementelor n.
(N, k) - colecțiile sunt numite combinații: cu repetarea unui număr fără repetiții. Rețineți că o combinație (n, k) fără repetiții este un subset k-element
Această regulă este suma sau regula alternativelor.
Dacă obiectul x Є X poate fi ales în n moduri și după fiecare dintre astfel de alegeri obiectul y Є Y poate fi ales în mod m, atunci alegerea perechii ordonate (x, y) se poate face în m n moduri.
configurații.
1. Numărul locurilor (n, k) fără repetiții poate fi determinat utilizând regula produsului.
§2.2. Chain. Cicluri. Conectivitate.
1. O secvență de vârfuri și muchii unui grafic G se numește o cale
§2.3. Copaci.
1. O margine e a unui grafic arbitrar G se spune că este ciclică dacă aparține cel puțin unui ciclu elementar din grafic și un ciclu aciclic
§2.5. Numărul ciclomatic.
1. Considerăm subgrafe care pot fi deconectate, dar care conțin toate vârfurile graficului. Fie G un grafic care conține marginile p numerotate (e1, e
§3.1. Prezentarea informațiilor.
Codificare - prezentarea informațiilor sub formă de semnale și caracteristicile acestora. Decodificarea este procesul invers. Un semnal poate prezenta informații sub forma harei sale
§3.3. Coduri redundante rezistent la zgomot.
În codurile binare non-redundante, în codurile Gray și în codurile construite pe carduri Carnot, orice eroare constă în denaturarea unui simbol sau a unui bit de cod
§3.4. Verificări cu paritate.
Ei au o mare eficiență și o redundanță redusă. Verificările cu paritate sunt construite astfel încât să se adauge un bit la combinația de coduri, ceea ce face numărul de unități de perechi de coduri
§3.5. Cod Hamming.
Codul Hamming se referă la coduri care permit nu numai detectarea, ci și corectarea erorilor unice. Capacitatea de corectare a codului se realizează datorită verificărilor multiple asupra parității
Doriți să primiți ultimele știri prin e-mail?
Articole similare
Trimiteți-le prietenilor: