In teoria grafurilor, graficul izomorfism și se numește bijectie între mulțimea de noduri astfel încât oricare două vârfuri și grafic sunt adiacente dacă și numai dacă vârfurile adiacente în coloană. Aici graficele neorientate sunt înțelese și nu au greutăți de noduri și muchii. În cazul în care conceptul este aplicat unui izomorfism grafice orientate sau ponderate impun restricții suplimentare privind păstrarea orientării și a valorilor ponderilor arcelor. Dacă este instalat izomorfismul grafic, acestea sunt izomorfe, și sunt denumite.
Uneori bijectie scris ca izomorfism de substituție. Unele sarcini de procesare grafic necesită nu numai un test de izomorfism, dar, de asemenea, determina substituirea acesteia.
Raportul a graficului izomorfism este o relație de echivalență. definit pentru graficele, și vă permite să facă o partiție din clasa originală a tuturor graficelor în clase de echivalență. Setul de grafice izomorfă reciproc, numit clasa graficului izomorfism (Eng.) Numărul în funcție de secvența reprezintă A000088 în OEIS (1, 1, 2, 4, 11, 34, 156, 1044, 12346.).
Dacă graficul bijectie se afișează pe sine (coloane și la fel), este numit o automorphism a graficului.
Două grafice sunt date în exemplul sunt izomorfe.
Izomorfism între grafice și
Grafic izomorfism de tip general
Este grafice izomorfe și, dacă prin permutarea de rânduri și coloane ale matricei graficului adiacență poate obține matricea de adiacenta. Cu toate acestea, căutarea tuturor permutărilor posibile caracterizate complexitate de calcul (cu condiția ca o comparație este făcută din matrici adiacenta pentru un timp care este independent de faptul că, în mod normal nedrept și mai departe crește valoarea redusă), care limitează în mod semnificativ utilizarea acestei abordări în practică. Există metode limitate de enumerare a posibilelor perechi vârfuri probabil-izomorfe (ramură analog și metodă legat), dar ele nu se îmbunătățesc în mod semnificativ asimptotic de mai sus [1].
Whitney teoremă
Excluderea din teorema Whitney a prezentat grafice (stânga) și (dreapta) nu sunt izomorfe, dar graficele lor de linie sunt izomorfe
Teorema Whitney grafice izomorfe ale [2] [3]. Hassler Whitney formulată în 1932. afirmă că două grafic conectat izomorfe dacă și numai dacă acestea sunt grafice liniare (Eng.) izomorfe cu excepția grafice (graficul complet de trei vârfuri) și graf bipartit complet, care nu sunt izomorfe, dar ambele au graficul sub formă de grafice linie. Whitney teorema poate fi generalizată pentru hipergrafuri [4].
invarianți
Există un set de grafice ale caracteristicilor numerice, numite invarianți. care coincid în graficele izomorfe (meci invariantă este necesară., dar nu suficientă pentru izomorfism) [5]. Acestea includ numărul de noduri și numărul de arce / marginile graficului G. ordonate în ordine crescătoare sau descrescătoare grade vertex vector ordine, ordonate ascendent sau descendent valori proprii grafic vector adiacență (spectrul graficului), numărul cromatic și altele. Coincidența invarianți fapt în mod normal nu poartă informații substituirea izomorfism.
Invariant se numește completă. În cazul în care un meci grafic invarianți este necesară și suficientă pentru a stabili izomorfismul. De exemplu, fiecare dintre valorile și (mini și matricea de adiacență maxi-cod) este invariant pentru grafic complet cu un număr fix de noduri.
Diverse invarianți au diferite de calcul complexitate. În prezent, invarianții grafic complete, calculabile în timp polinomial nu este cunoscut, cu toate acestea, nu a fost dovedit că el nu există. Încercările de a găsi în mod repetat, a fost făcută în anii '60 - '80 ai secolului XX. dar ei nu au avut succes.
produs modular Vizinga
produs modular de grafice, oferite VG Vizing (Eng.) Se ne permite să reducem problema testării izomorfism la problema determinării densității unui grafic care conține vârfuri. În cazul în care, atunci graficul conține un subgraf izomorf grafic.
Grafic izomorfism de un tip special
Vezi ce „Graph izomorfism“ în alte dicționare:
Izomorfism - În acest termen, există alte utilizări, vezi izomorfismul (dezambiguizare) .. Izomorfism (de la alții. Gr. Ἴσος «egal, identic, similar“ și μορφή «formă") este un concept foarte general, care este utilizat în diferite domenii ale matematicii. Comună ... ... Wikipedia
Grafic izomorfism - relație de echivalență pe set de grafice. cartografiere izomorfă a unui graf neorientat într-un alt este numit. o cartografiere de noduri și muchii ale unui grafic, nervuri respectiv vershinyi un alt grafic pentru k rom ... ... matematică Enciclopedia
Izomorfism (matematică) - izomorfism este un termen foarte general, care este utilizat în diferite ramuri ale matematicii. În general, se poate fi descrisă după cum urmează: Să presupunem că cele două seturi sunt date cu o anumită structură (grupuri, inele, spațiu linie, etc ...). Bijectie între ... ... Wikipedia
Izomorfism (Mat.) - izomorfism este un concept foarte general, care este utilizat în diferite domenii ale matematicii. În general, se poate fi descrisă după cum urmează: Să presupunem că cele două seturi sunt date cu o anumită structură (grupuri, inele, spațiu linie, etc ...). Bijectie între ... ... Wikipedia
Numără Homeomorphisms - relație de echivalență pe setul de grafice care descriu geometria și proprietățile lor. G. a fost determinat mod sleduyupshm. coaste subdiviziune (a, b) .grafa Gnaz. margini de operare care constă în adăugarea unui nou vârf v, eliminarea (a, b) .i ... ... matematică Enciclopedia
Teoria grafurilor - grafic cu șase vârfuri și șapte muchii grafic teoria secțiune a matematicii discrete, care studiază proprietățile grafice. In termeni generali, graficul este reprezentat ca un set de noduri (noduri) conectate de margini. În mod strict ... Wikipedia
Teoria grafurilor și mografov - Teorema 3.27. înlocuind orice muchie (a, b) în graficul G la Gkriticheskogo k vertex arce disjunctă lungime 3 dacă și numai dacă rezultatul în formarea graficului critice T 3 (G), unde k satisface una dintre următoarele condiții: # k = 1 ... Wikipedia
Glosar de teoria grafurilor - Această pagină glosar. . A se vedea, de asemenea, articolul principal: Teoria grafurilor Aici sunt colectate definițiile teoriei graficului. Italicele indică trimiterile la termenii din dicționar (pe această pagină) ... Wikipedia
Glosar de teoria grafurilor - conține definiții ale teoriei graficului. Italicele indică trimiterile la termenii din dicționar (pe această pagină). # A B C D E F G H I J K L M N O P Q R S ... Wikipedia
Doug (teoria grafurilor) - conține definiții ale teoriei graficului. Italicele indică trimiterile la termenii din dicționar (pe această pagină). # A B C D E F G H I J K L M N O P Q R S T U V ... Wikipedia