【グラフ理論とネットワーク理論】Extended Complete Graph

Connectivity and Damage Index

Connectivity

Connectivity express the reliability of the graph

• Node Connectivity Cv(G) : Minimum number of nodes to be removed to make a graph unconnected.
• Branch Connectivity Ce(G) : Minimum number of branches to be removed to make a graph unconnected.
• Node connectivity = d → d - 1 node failures OK
• Branch connectivity = d → d - 1 branch failures OK

Theorem1

Cv(G) ≦ Ce(G) ≦ δ(G) : δ = degree (the number of branches of one node)

Damage index

Damage index is an index of the increase of hops to connect in case of failure.

α-Node(Branch) Damage Index Iα(G) (Jα(G)) is defined as blow

Maximum diameter of a graph without α nodes(branches) - Diameter of the original graph G

Design Method of Extended Complete Graph

Extended Complete Graph : Complete graph Gd → Line conversion, m times → Extended complete graph.

L^m(Gd) = L(L(…(L(G))…)) (m times)

Ex. 1

	Number of nodes	Number of branched
Gd	d+1	(d+1)d
L(Gd)	(d+1)d	(d+1)d2
L2(Gd)	(d+1)d2	(d+1)d3

Comparison

	Complete graph	Extended Complete Graph
正則性 Regularity	d-Regular	d-Regular
Number of nodes V	d + 1	(d + 1)dm
Number of branches E	(d + 1)d	(d+1)dm+1
直径 Diameter k(G)	1	m+1
Node connectivity Cv(G)	d	d
Branch connectivity Ce(G)	d	d
次数 Degree δ(G)	d	d
節点罹障度 Node damage index Iα(G)	0	≦ m
枝罹障度 Branch damage index Jα(G)	1	≦ m+1

Throughput ratio in case of failure

k(G)/(Jα(G) + k(G)) → 0.5 for both Gd and L^m(Gd)