Isomorfisme de grafos
En teoria de grafos, un isomorfisme de grafos és una biyección dels vèrtiços d'un grafo sobre un atre, de modo que es preserva la adyacencia dels vèrtiços. Més formalment, l'isomorfisme entre dos grafos G i H és una biyección f entre els conjunts dels seus vèrtiços que preserva la relació de adyacencia.[1] És dir, qualsevol parell de vèrtiços o i v de G són adjacents si i solament si ho són les seues imàgens, f(o) i f(v), en H.
A pesar del seu diferent aspecte, els dos grafos que es mostren a continuació són isomorfos:
| Grafo G | Grafo H | Un isomorfisme entre G i H |
|---|---|---|
|
|
|
Dos grafos en matrius de adyacencia respectives A i B seran isomorfos si i solament si existix una matriu permutació P tal que B = P A Pt.[2]
Problema de l'isomorfisme de grafos
[editar | editar còdic]- Artícul principal → Problema d'isomorfisme de subgrafos.
La determinació de si dos grafos en el mateix número de vèrtiços n i arestes m són isomorfos o no, es coneix com el problema de l'isomorfisme de grafos. Este problema admet un atac per força bruta que exigiria comprovar si les n! biyecciones possibles preserven la adyacencia, pero no es coneix un algoritme eficient, a lo manco per al cas general. En este context, eficiència deu interpretar-se com a creiximent del número de passos inferior a O(in).
El problema de l'isomorfisme de grafos presenta una curiositat en teoria de complexitat computacional en ser un dels pocs problemes citats per Garey i Johnson en 1979 pertanyents a NP dels que es desconeix si és resoluble en temps polinòmic o si és NP-complet (actualment està en revisió la demostració de que el problema està en P).[3]
Aplicacions
[editar | editar còdic]En anàlisis de rets socials, els estudis de díadas i tríades en rets socials es basen en isomorfismes de subgrafos molt menuts.[1]
Vore també
[editar | editar còdic]Referències
[editar | editar còdic]- ↑ 1,0 1,1 Wasserman y Faust, 2013, «Grafos i matrius» (per Dawn Iacobucci), pp. 121-188.
- ↑ Jonathan L. Gross, Jay Yellen.Handbook of Graph Theory. CRC Press, 2004. ISBN 158488090
- ↑ *
Bibliografia
[editar | editar còdic]- (2013) Anàlisis de rets socials: Métodos i aplicacions, Madrit: Centre d'Investigacions Sociològiques. OCLC 871814053. ISBN 978-84-7476-631-8.
Referències
[editar | editar còdic]
- Este artícul conté una traducció derivada de «Isomorfismo de grafos» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.