2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 помогите найти источник с доказательством
Сообщение26.01.2016, 11:57 
Здравствуйте. Пожалуйста помогите найти источник (статью, книгу, диссертацию и т.п.) в котором есть доказательство того, что эксцентриситеты двух смежных вершин или равны, или отличаются друг от друга не более чем на 1.
В интернете нашел вот такой отрывок:
Цитата:
Math 481 - Summer 2012
Final Exam
You have one hour and fifty minutes to complete this exam. You are not allowed to use any
Electronic device. Be sure to give reasonable justification to all your answers.
1. …………………………………………
2. If u and v are adjacent vertices in a graph, prove that their eccentricities differ by at most one.
Suppose that $u_1$ and $v_1$ are vertices such that $ecc(u) = d(u, u_1)$ and $ecc(v) = d(v, v_1)$. We know That $d(u, u_1) \leqslant  d(v, u_1) + 1$;
Otherwise there would be a shorter route from u to u1 by going through v. Similarly,
$d(v, v_1)  \leqslant  d(u, v_1) + 1$
Note that
$$ecc(u) = d(u, u_1) \leqslant  d(v, u_1) + 1 \leqslant  ecc(v) + 1;$$
$$ecc(v) = d(v,  v_1)  \leqslant  d(u, v_1) + 1 \leqslant  ecc(u) + 1;$$
so
$$ecc(u) \leqslant  ecc(v) + 1  and  ecc(v) \leqslant  ecc(u) + 1;$$
or
$$1 \leqslant  ecc(u)   ecc(v) \leqslant  1;$$
which means that the difference between $ecc(u)$ and $ecc(v)$ is at most one.

Я так полагаю, что это - отрывок из какого-то учебного курса. А мне нужна ссылка на источник, в котором есть это доказательство. Буду безмерно благодарен за любую хорошую ссылку. :-)

 
 
 
 Re: помогите найти источник с доказательством
Сообщение26.01.2016, 13:19 
Аватара пользователя
Доказательство настолько очевидно, что его предлагают найти самостоятельно в качестве упражнения в книге https://books.google.ru/books?id=DfcQaZKUVLwC&pg=PA21&lpg=PA21#v=onepage&q&f=false (задача 1.2.1.5 на стр. 21).

А здесь приведено решение этой задачи (пункт 3).

 
 
 
 Re: помогите найти источник с доказательством
Сообщение26.01.2016, 13:57 
whitefox
Большое спасибо. Второй отрывок я уже видел.
Безуспешно искал HHM (думал, что это краткое название книги).
А оказалось, что аббревиатура HHM 1.2.1.5, p.21 это имена авторов книги.
Еще раз спасибо. :D

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group