про граф

[germ9c]

Доказать, что любой граф допускает такую геометрическую реализацию в трёхмерном пространстве, при которой его ребрам отвечают прямолинейные отрезки

[Xaositect]

Докажите индукцией по числу вершин, для этого докажите, что множество "плохих" точек (в которых ребра из последней вершины будут пересекать какие-то предыдущие ребра) не может быть всем пространством.

[chessar]

1) Реализовать $|V|$ точек, соответствующих вершинам графа, на одной прямой.
2) Провести через эту прямую $|E|$ различных полуплоскостей ($E$ - число рёбер графа).
и
3) Реализовать каждое ребро в своей полуплоскости.

[Xaositect]

chessar в сообщении #792090 писал(а):

1) Реализовать $|V|$ точек, соответствующих вершинам графа, на одной прямой.
2) Провести через эту прямую $|E|$ различных полуплоскостей ($E$ - число рёбер графа).
и
3) Реализовать каждое ребро в своей полуплоскости.

Нужны прямолинейные ребра, так не получится.

[chessar]

Xaositect в сообщении #792091 писал(а):

chessar в сообщении #792090 писал(а):

1) Реализовать $|V|$ точек, соответствующих вершинам графа, на одной прямой.
2) Провести через эту прямую $|E|$ различных полуплоскостей ($E$ - число рёбер графа).
и
3) Реализовать каждое ребро в своей полуплоскости.

Нужны прямолинейные ребра, так не получится.

Да, действительно не получиться - упустил прямолинейность в условии.

[germ9c]

Берем множество вершин графа. Это конечное множество. Ставим ему в соответствие конечное множество точек трехмерного пространства. Соединяем отрезками.

такое доказательство пойдет?)

[svv]

Xaositect рассказал, как решать проблему, с которой Вы еще не столкнулись: от реализации графа естественно требовать, чтобы ребра пересекались только своими концами в нужных вершинах — чтобы не было «левых» пересечений. Надо доказать, что для любых самых запутанных графов возможно избежать таких нежелательных пересечений.