Esiste un nome per un grafico ad albero, in cui i nodi possono avere più genitori, ma sempre da un solo livello sopra.Esiste un nome per un grafico ad albero, in cui i nodi possono avere più genitori, ma sempre da un solo livello superiore a
Quindi il grafico è diretto e aciclico, ma ha anche altri vincoli.
Ciò significa anche che tutti i percorsi da qualsiasi nodo particolare alla radice hanno la stessa lunghezza.
Credo che questo sia chiamato layered graph. Un grafico di questo tipo è un grafico in cui è possibile dividere i nodi in gruppi L , L , ..., L n tale che ogni bordo (u, v) va da qualche strato L i a un secondo livello L i + 1.
Spero che questo aiuti!
Se la mia affermazione sui percorsi verso la radice è corretta, anche questa è corretta, a parte questo consente più nodi radice (un intero livello radice) a cui non avevo pensato. Tuttavia, ho pensato ad un'interpretazione alternativa della definizione degli OP in cui un nodo può avere più genitori, ma quei genitori devono essere fratelli (non solo nello stesso livello, ma condividere lo stesso genitore che è il nonno originale dei nodi). Dipende dall'intento del vincolo "un livello sopra". – Steve314
Una parte - penso di poter rideterminare la regola aggiuntiva come "tutti i percorsi da qualsiasi nodo particolare alla radice sono della stessa lunghezza". Non sono sicuro che continuerò a pensare "e se un nodo ha un link genitore che salta a un nonno, ma il nonno ha un link genitore che si collega a un fratello?" ma sono abbastanza certo che è impossibile. Dato che il "livello" di un nodo è (presumo) puramente implicito nella struttura, tali relazioni non possono accadere senza violare la regola all-paths-stessa-distanza-da-radice per un nodo o un altro. – Steve314
Grazie Steve. Inoltre, perché è un loro voto ravvicinato? – alan2here
Forse fuori tema. Ho svalutato perché sono curioso, ma solo perché una domanda è interessante non significa che appartenga qui. I nomi di particolari tipi di grafici possono essere più adatti allo scambio di pile matematiche. – Steve314