Operațiuni algebrice
Din moment ce graficul constă din două seturi (vârfuri și muchii), atunci diferite operații pe seturi generează în mod natural operațiile corespunzătoare pe grafice. De exemplu, unirea a două grafice este definită ca un grafic cu ,, și intersecția ca un grafic al cărui. Ambele operații sunt ilustrate în Fig. 1.12.
O adăugare (un grafic suplimentar) la un grafic este un grafic al cărui set de vârfuri este același cu y, iar mulțimea de margini este complementul mulțimii setului tuturor perechilor neordonate de vârfuri. Cu alte cuvinte, două grafuri diferite sunt adiacente în grafic dacă și numai dacă nu sunt adiacente în grafic. De exemplu ,. Un alt exemplu este prezentat în Fig. 1.13. Evident, întotdeauna.
Prin suma a două grafice abstracte înțelegem unirea de grafice cu seturi disjuncte de vârfuri. Mai exact, se înțelege următorul. Mai întâi, vârfurile sumelor grafice sunt date de nume (notații, numere) astfel încât seturile de vârfuri nu se intersectează, atunci graficele rezultate sunt combinate. Funcția de adăugare este asociativă, adică pentru oricare trei grafice. Prin urmare, puteți forma suma oricărui număr de grafice, fără a specifica ordinea acțiunilor cu ajutorul parantezelor. Dacă se adaugă copii ale aceluiași grafic, atunci graficul rezultat este notat cu. De exemplu ,. În Fig. 1.14 graficul este prezentat.
Conectarea a două grafice este numită grafic. obținute din suma lor prin adăugarea tuturor marginilor care leagă vârfurile primului summand de vârfurile celei de-a doua. Vom scrie această operație ca. În Fig. 1.15 graficul este prezentat. Este ușor de observat că operațiile de adăugare și conectare a graficelor sunt legate una de alta prin următoarele relații simple:
Introducem încă două tipuri de grafice speciale, care sunt descrise cu ușurință utilizând operația de conectare. Primul este un grafic complet bipartit. În acest grafic, mulțimea de vârfuri este împărțită în două subgrupe (părți), dintre care unul este vârful în celălalt și cele două noduri din el sunt adiacente dacă și numai dacă aparțin unor subseturi diferite. Al doilea este roata. În Fig. 1.16 graficele și.
Produsul graficelor este definit după cum urmează. Setul de vârfuri al unui grafic este produsul cartezian al mulțimilor și, adică vârfurile acestui grafic, sunt ordonate perechi, unde este vârful primului factor, este vârful celui de-al doilea. Vârfurile și sunt adiacente dacă și numai dacă sunt adiacente în grafic sau sunt adiacente în grafic. Utilizând funcționarea produsului, puteți exprima câteva grafice importante prin cele mai simple. De exemplu, produsul celor două lanțuri dă o latură dreptunghiulară (a se vedea Figura 1.17). Dacă unul dintre factori este transformat într-un ciclu, adăugând o margine. atunci rețeaua dreptunghiulară se transformă într-o rețea cilindrică. Și dacă cel de-al doilea factor este transformat într-un ciclu, atunci obținem o latură toroidală.
Un alt exemplu este un cub dimensional definit după cum urmează. Vârfurile sale sunt tot felul de seturi de lungimi binare ordonate. În total, astfel, în acest grafic al nodurilor. Vârfurile sunt adiacente în ea dacă și numai dacă seturile diferă exact într-o singură coordonată. Utilizând funcționarea produsului, graficul poate fi definit recursiv:
În Fig. 1.18 arată cum să ajungi.
Articole similare
Trimiteți-le prietenilor: