7. Pentru fiecare din următoarele relații binare, investigați dacă este definit peste tot, funcțional; răspundeți la răspuns.
8. Indicați toate reprezentările surjective ale setului A = pe setul B =. Există vreo mapare injectabilă a lui A în B?
9. Găsiți toate mapările setului A = în sine, indicați care dintre ele sunt injective, surjective.
10. Fie f o mapare a unui set finit A în sine. Dovada că f este injectiv dacă și numai dacă atunci f este surjectiv.
literatură
5. Lecție practică 5
Subiect: "Elemente ale graficului. Modalități de alocare a unui grafic. Subgrafurilor.
Isomorfism »
Scopul lecției:
concepte de absorbtie, cum ar fi un grafic, vârfurile graficelor și muchii, orientate și neorientate grafic multigraf pseudograph, adiacenta, incidenta, matricea de adiacenta izomorfism și incidența, un grafic bipartit, graficul plin, picurile grad subgrafic.
Explicarea muncii
Timpul pentru asignarea practică este de 2 ore.
1. Pe baza materialului teoretic de mai sus, răspundeți la următoarele întrebări:
Pe ce vârfuri ale unui grafic se spune că sunt adiacente?
Care este conceptul de incidență?
Cum se stabilește matricea de incidență pentru digraf?
Ce grafic este numit un pseudograf?
Ce grafic este numit bipartit?
2. Definiți următoarele concepte:
3. Completarea sarcinilor pentru activitățile din clasă.
4. Sarcini complete pentru munca independenta.
5.1. Elemente ale graficului
Un grafic G este o colecție de două seturi: un set de vârfuri ne-goale V = v 1, v 2. vn> și mulțimea de muchii (arce) E = e 1, e 2. en>. Astfel, G = (V.E), V1 Æ, E Ì V × V.
Dacă (v 1, v 2) - perechi ordonate (.. Ie arc), apoi v 1 este numit la început, o v 2 - capăt al arcului este, în cazul în care v 1, v 2> -. Pereche neordonată, margine e se numește neorientat. La fiecare grafic G se poate asocia un grafic G nedirectat corelat cu aceleași seturi V și E și incidențe, dar toate perechile sunt dezordonate. Un astfel de grafic este numit asociat. Vârful, care nu intră în contact cu nicio margine, se numește izolat. Un vârf incidente la exact o margine, iar marginea însăși se numește terminal sau agățat. O margine cu capete potrivite se numește o buclă. Se spune că două vârfuri care intră pe aceeași margine sunt adiacente. Două margini care intră în același vârf sunt considerate a fi învecinate. Marginile care corespund aceleiași perechi de vârfuri se numesc multipli sau paralel.
Un grafic care conține mai multe margini este numit multigraf. O margine nedirecționată a unui grafic este echivalentă cu două arce direcționate opus care leagă aceleași vârfuri. Un grafic cu multiple muchii și bucle este numit un pseudograf.
În Fig. 3 prezintă: un pseudograf orientat cu 7 vârfuri și 6 arce și un multigraf neorientat având 4 vârfuri și 5 margini. Să ilustrăm câteva dintre conceptele introduse.
Pentru digraf (figura 3a): v 1, v 2, v 3, v 4, v 5, v 6. v 7 - noduri (noduri); v 5 - vertex izolat; v 1, v 4 - terminale (suspendate); v 2 și v 3, v 2 și v 1 sunt perechi de vârfuri învecinate; e1, e2, e3, e4, e5, e6 sunt muchiile orientate (arce); e 2 și e 3 - arce paralele (multiple); e 2 și e 1 sunt arce adiacente; e 6-bucla pentru digraph.
Pentru grafic (figura 3b): v 1, v 2, v 3, v 4 - noduri; v vârf 4 - terminal (agățat); v 2 și v 3, v 2 și v 1 sunt perechi de vârfuri învecinate; e1, e2, e3, e4, e5 sunt muchii (arce); e 4 și e 5 sunt muchii paralele (multiple); e 2 și e 3 sunt marginile contigue; buclele nr.
5.2. Modalități de specificare a graficelor
1. Listează (listați) marginile graficului cu indicarea capetelor lor și adăugând o listă de vârfuri izolate.
2. Matricea de adjuvant A = (aij) este definită identic pentru grafice orientate și nedirecționate. Aceasta este o matrice pătrată de ordin n. unde n este numărul de noduri pentru care
Matricea de incidență B = (bij) a unui grafic orientat este matricea (n 'm), unde n este numărul de vârfuri, m este numărul de muchii pentru care
Pentru un grafic nedirecționat, matricea de incidență B este definită după cum urmează:
Bucla corespunde unui element egal cu 2.
Matricele de contiguitate și incidența graficului descris în Fig. 3a. au forma (figura 4):
3. Pentru claritate, graficul este reprezentat sub forma unui obiect geometric: nodurile corespund diferitelor puncte selectate din spațiu (în plan), marginile sunt segmentele de curbe care leagă vârfurile.
Luați în considerare câteva varietăți de grafice.
Un graf neorientat G = (V. E) - bipartite dacă mulțimea vârfurilor V poate fi împărțit în două subseturi V 1 și V 2 că fiecare nervură are un capăt în V 1 și celălalt în V 2. Dacă fiecare dintre nodurile clasa V 1 conectată margine la fiecare vârf V clasa 2, atunci graficul bipartit complet este notată cu K, și m, n, unde m = | V 1 | n = | V 2 |. În Fig. Figura 5a prezintă un grafic bipartit, în Fig. 5b și 5c sunt grafice bipartite complete de K 3.2 și K 3.3.
Un grafic complet este un grafic fără margini multiple (și uneori fără bucle) în care oricare două vârfuri sunt conectate printr-o margine (orientată sau nedirecționată). Un grafic complet nedirecționat cu n noduri este notat cu Kn. Evident, graficul Kn conține n (n - 1) / 2 margini.
În Fig. 6a. Figurile 6b și 6c prezintă diagramele K3, K4, K5, respectiv. În Fig. 6d prezintă de asemenea graficul complet.
5.3. subgrafurilor
Graficul G ¢ = (V ¢, E ¢) se numește subgraful graficului G = (V, E). notație: G ¢ Í G. dacă V ¢ Í V. E ¢ Í E și pentru incidentele seturilor V 'și E' ale graficului G sunt conservate. În mod clar, fiecare margine a lui E 'intră în subgraful G ¢ împreună cu punctele sale finale. Un subgraf este numit potrivit. dacă este diferit de graficul propriu-zis.
Un exemplu. Graficele din Fig. 7b și 7c sunt subgrafurile graficului din Fig. 7a.
5.4. Graf izomorfism
Două grafice G 1 = (V 1, E 1) și G 2 = (V 2, E 2) sunt izomorfe dacă între nodurile lor există bijectie j: V 1 ® V 2 astfel încât pentru orice pereche de noduri u, v din V 1 marginea (u, v) Î E1 "marginea (j (u), j (v)) Î E2.
Un exemplu. Graficele prezentate în Fig. 8, sunt izomorfe.
Graficele izomorfice diferă numai prin numerotarea vârfurilor. Matricile de contiguitate a două grafice izomorfe pot fi obținute una de alta prin permutarea rândurilor și coloanelor. Pentru a afla dacă două grafice sunt izomorfice, trebuie efectuate toate permutările posibile ale rândurilor și coloanelor matricei de adjuvantă a unuia dintre grafice. Dacă, după o anumită permutare, se obține matricea de adiacentă a celui de-al doilea grafic, atunci aceste grafice sunt izomorfe. Pentru a verifica dacă graficele nu sunt izomorfice, toate n trebuie să fie satisfăcute. posibile permutări ale rândurilor și coloanelor.
5.5. Gradele de vârfuri ale unui grafic
Gradul de vârf v al graficului G este numărul d (v) al marginilor graficului G. care intră în punctul v. Un vârf al unui grafic cu gradul 0 este numit izolat, iar gradul 1 este suspendat.
În cazul unui pseudograf nedirecționat, se presupune că contribuția fiecărui incident la o anumită vertex v. în d (v) este egal cu 2 (în timp ce contribuția oricărui alt incident la marginea v este 1).
Outdegree (abordare) a vertex v este numărul de digraph D + d (v) (d- (v)) digraph D. arce care provin de la vertex v (intrare la vertex v).
În cazul unui pseudograf orientat, contribuția fiecărui incident la anumite vertex v. în d (v) este egal cu 1, ca în d + (v) și în d- (v).
În graficul G (figura 3b), gradul vârfului v 1 este de patru, adică d (v 1) = 4; vârf v 4 - agățat, deoarece d (v 4) = 1. Într-un pseudographs direcționat (. Figura 3a) Gradul de vârf v 6 este de trei, și anume, d (v 6) = d + (v 6) + (d- .. (v 6) = 2 + 1 = 3, vârf v 1 - agățat, deoarece d (v 1) = 1, vârf v 5 - Izolarea, deoarece d (v 5) = 0.
Pentru activitățile din clasă
1. Graficele sunt realizate (figura 9). Care sunt aceste grafice? Descrieți principalele caracteristici ale acestora. Dați exemple de elemente grafice.
Trimiteți-le prietenilor: