Combinatorial graph complexity

Minoli, Daniel

Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti, Tome 59 (1975), p. 651-661 / Harvested from Biblioteca Digitale Italiana di Matematica

Résumé

Qui si ottiene una misura della complessità di un grafo non orientato; varie misure sono già state proposte, ma esse non soddisfano ad alcune proprietà fondamentali che una siffatta funzione dovrebbe avere, date essenzialmente dal carattere monotonico della complessità rispetto al numero dei vertici, dei lati, e del grado di connessione del grafo. Ecco la nostra definizione: Un cammino tra due vertici $v_{i}$ and $v_{j}$, $v_{i} \ne v_{j}$, dicesi proprio se 1) contiene $v_{i}$ e $v_{j}$ esattamente una volta, rispettivamente come vertice inziale e finale, e 2) contiene ogni particolare lato al massimo una volta; la complessità $\chi(G)$ di un grafo $G$ viene quindi così definita: $$\chi(G) = \frac{ne}{n+e} \,\, \sum_{(v_{i},v_{j}),i<j} \, \sigma_{ij},$$ dove $e$ = numero dei lati, $n$ = numero dei vertici, $\sigma_{ij}$ = numero dei cammini propri tra i vertici $v_{i}$ e $v_{j}$. Proprietà di questa complessità vengon qui investigate.

Détail

Publié le : 1975-12-01

MR 0476578 | Zbl 0361.05046

Bibliographie

[1] Marshall, C. W. (1971) - Applied Graph Theory, Wiley-Interscience, New York. | MR 323595 | Zbl 0226.05101

[2] Mowshowitz, A. (1968) - Entropy and the Complexity of Graphs. II, «Bull. Math. Biophys.», 30, 225-240. | MR 244083 | Zbl 0165.57602

[3] Trucco, E. (1956) - A Note on the Information Content of Graphs, «Bull. Math. Biophys.», 129-135. | MR 77919

[4] Minoli, D. - Graph Complexity, Unpublished Thesis.