Медиана графа

Пусть дан граф . Для каждой вершины определим два числа, которые называются передаточными числами:

и (2.3)

,

где - кратчайшее расстояние от вершины до вершины .

Вершина , для которой

,

называется внешней медианой графа G, а вершина , для которой

,

называется внутренней медианой графа G.

Рассмотрим граф, изображенный на рис. 2.1, и вычислим внешние и внутренние передаточные числа вершин. Эти числа приведены в прикрепленном столбце к матрице и прикрепленной строке к матрице .

=		x1	x2	x3	x4	x5	x6
	x1	0	15	30	18	36	39	138
	x2	18	0	5	8	16	24	71
	x3	24	21	0	6	20	27	98
	x4	18	12	25	0	8	18	81
	x5	14	6	15	12	0	12	59*
	x6	6	24	45	24	40	0	139

=		x1	x2	x3	x4	x5	x6
	x1	0	10	12	18	18	26
	x2	27	0	3	12	12	24
	x3	60	35	0	15	25	45
	x4	18	8	10	0	4	12
	x5	28	8	12	24	0	16
	x6	9	24	27	36	30	0
		142	85	64*	105	89	123

По полученным передаточным числам видно, что внешней медианой является с , а внутренней - , с внутренним передаточным числом, равным 64.