Graflarda bazı zedelenebilirlik ölçümleri ve aralarındaki ilişkiler

Bir ağın (iletişim, bilgisayar, elektrik, ulaşım vb.), belli merkezleri ya da bağlantı hatları zarar görmesinden sonra iletişim kesilene kadar ağın göstermiş olduğu dayanma gücünün ölçümüne zedelenebilirlik denir. Bir ağın, zedelenebilirlik değerinin belirlenebilmesi için merkezleri bir grafın tepelerine, bağlantıları grafın ayrıtlarına karşılık gelecek şekilde bir graf ile modellenir. Bağlantılı bir G grafının ayrıt komşuluk kopma derecesi, S bir ayrıt subversion stratejisi, G/S grafındaki bileşen sayısı w(G/S) ve en büyük boyutlu bileşenin tepe sayısı m(G/S) olmak üzere ENR(G)=max┬(S⊆E(G) )⁡〖{w(G/S)-|S|-m(G/S) ∶ w(G/S)≥1}〗 olarak tanımlanır. Diğer taraftan, bağlantılı bir G grafının ayrıt saçılım sayısı, S ayrıt kesim kümesi, G-S grafındaki bileşen sayısı w(G-S) olmak üzere es(G)=max┬(S⊆E(G) )⁡{w(G-S)-|S| ∶ w(G-S)>1} olarak tanımlanır. Bu tezde bilinen bazı özel graf yapıları için ayrıt komşuluk kopma derecesi ve ayrıt saçılım sayısı değerleri hesaplanmıştır. Son kısımda bu ölçümler arasında ki ilişkiler verilmiştir.