Случайные бесконечные графы
brandt1
Факт, который меня удивил: почти все графы на счетном множестве вершин изоморфны. Более точно: построим случайный граф , т.е. любые две вершины с вероятностью одна вторая соединим ребром. Существует такой универсальный граф, что случайный граф изоморфен ему с вероятностью 1. Доказательство (очень схематичное) см. в http://e-books.enigma.uran.ru/book_djvu/erdjosh/erdjosh.djvu
Этот универсальный граф определяется с точностью до изоморфизма следующим свойством. Пусть даны 2 конечных непересекающихся множества вершин U и V. Тогда найдется такая вершина w, которая соединена со всеми вершинами из U и не соединена со всеми вершинами из V. См. также
http://en.wikipedia.org/wiki/Random_graph

?

Log in