Извините, если это основной вопрос, но мне было интересно, может ли кто-нибудь помочь мне выяснить класс проблем, к которым относится мой конкретный вопрос.Я искал любые стандартные метрики, которые можно использовать для сравнения графиков разного размера и связности.В частности, рассмотрим следующий пример:
G1 G2
2 D
| / \
4 --- 1 --- 3 C -- A1 - A2 -- E
|
5
Что меня интересует, так это охватить понятие устойчивости внутри одного графа (интрастабильность) и относительно другого графа (интерстабильность).Например,
Стабильность внутри:
В G1, в моей гипотетической метрике, 2,3,4,5 все имеют одинаковый эффект, если их удалить изграф.В G2, C,E будет иметь такой же эффект, но D будет иметь больший эффект.Тем не менее, A1,A2 будет иметь больший эффект, если они будут удалены.Что я ищу здесь, так это понятие устойчивости графа.Я предполагаю, что я мог бы просто использовать степень каждого узла, чтобы зафиксировать эффект определенного узла, но я не уверен, как рассчитать его для всего графа per se.
Взаимозаменяемость:
Можем ли мы что-то сказать о G1 и G2 в относительном смысле, то есть что-то вроде, потому что G1 имеет метрику стабильности X, а G2 имеет Y и потому что X < Y мы заключаем, что G1 менее стабильно, чем G2?Само определение стабильного остается открытым, но я пытаюсь понять, насколько ненадежен график или насколько он зависим от одного узла.
Может ли кто-нибудь указать мне правильное направление, чтобы иметь возможность количественно оценить этоили хотя бы как называется эта проблема?