Che cosa significa per due alberi binari di essere isomorfo?

Question

Che cosa significa per due alberi binari da isomorfi? Ho cercato on-line e non riesco a trovare una spiegazione chiara.

Per quanto ho capito, due alberi sono isomorfi se hanno la stessa forma. Così sto cercando di indovinare due alberi identici che può contenere diversi valori nei nodi.

Answer 1

Isomorphic deriva dalla "stessa forma" greca (come isobara è punti con la stessa pressione dell'aria e poligono significa "molti lati") in modo la vostra comprensione è corretta. Ma non fare l'errore di assumere forma in questo caso è un fisico forma (come l'albero ha una radice, un nodo di sinistra e di destra di un nodo, si veda sotto per esempio). I matematici hanno il loro linguaggio che solo a volte ha un rapporto di passaggio a Inglese: -)

Non sono solo alberi binari. In matematica, due strutture sono isomorfi se le loro proprietà sono conservati a prescindere dalla loro espressione (si può avere una funzione che si traduce da A a B e un altro da B ad A, senza perdita di informazioni).

Per il vostro caso particolare, è l'informazione nella struttura che è conservato. Ad esempio, se tali informazioni sono gli elementi ordinati {1,2,3}, poi l'albero non deve essere lo stesso fisico forma a tutti - le seguenti due sarebbe isomorfo:

  2      1
 / \      \
1   3      2
            \
             3

Un elenco ordinato collegato (o array ordinato, se è per questo) è anche isomorfo a quelle in quanto, in tal caso, nessuna informazione sarebbe perso nelle trasformazioni tra i due.

Se l'albero binario è stato utilizzato in un modo in cui ordinamento era irrilevante (cioè, una sorta "sacchetto" del contenitore), allora l'informazione sarebbe solo il contenuto in qualsiasi ordine, e tutte le seguenti sarebbe isomorfo (che secondo ultimo è solo una borsa, l'ultimo è una lista):

  2      1           2   3                   +---+  +---+  +---+
 / \      \         /     \      +-------+   | 3 |->| 1 |->| 2 |
1   3      2       1       2     | 1,3,2 |   +---+  +---+  +---+
            \     /         \    +-------+
             3   3           1

Naturalmente, un albero non ordinato può essere considerato un po 'di rifiuti a seconda delle esigenze, ma non è rilevante per questa particolare discussione.

Answer 2

A seguito di condizioni devono adempiere a due alberi di essere isomorfi:
1. Two Tree sono isomorfi se e solo se conservano stesso numero di livelli e stesso numero di vertici in ogni livello.

2.Two alberi sono isomorfi se e solo se hanno lo stesso spettro di laurea.

3.Two alberi sono isomorfi se e solo se hanno lo stesso grado di spettro ad ogni livello.

4. nessuna totale di foglia discendente di un vertice e il numero del livello di vertice sono entrambi albero albero isomorfi invariante.

In parole semplici:
Due alberi sono isomorfi se un albero può essere ottenuta da altri per eseguire qualsiasi numero di lanci cioè scambiando bambini sinistra e bambini destro di un numero di nodo.

Esempio di alberi isomorfi:

Ref: 1. http://www14.in.tum.de/konferenzen/ Jass03 / presentazioni / eterevsky.pdf 2. http://www.geeksforgeeks.org/tree-isomorphism-problem/

Answer 3

Credo che la vostra comprensione è più o meno corretta. Se si ignorano i valori e basta guardare la struttura, allora per ogni nodo nel primo albero ci deve essere un corrispondente nodo dell'altro albero e viceversa.

Naturalmente, entrambi gli alberi avrebbero lo stesso numero di nodi. Inoltre, è possibile scrivere un algoritmo (super-naive) per confermare questo isomorfismo tentando tutte le possibili funzioni di mappatura, e garantire che per ogni nodo del primo albero che viene mappato a un nodo all'altro, la mappatura corrispondente avviene con la genitori e con i due figli. Ci sono, ovviamente, algoritmi efficienti per verificare la presenza di questo.

Si può trarre beneficio dalla lettura sulla grafico isomorfismo prima; alberi sono un caso particolare (e più facile da risolvere) dal momento che non hanno cicli.