2014 dxdy logo

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

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




 
 Простой путь в графе
Сообщение01.09.2012, 23:05 
Простой путь - это последовательность дуг, в которой каждая следующая дуга имеет началом конец предыдущей и каждая дуга встречается не более одного раза (если отказаться от второго условия и допустить повторы вершин или дуг в пути, то граф называется путем - без слова "простой").
До этого граф определялся как тройка $(M,N,T)$, M - вершины, N - дуги, $T: N \to M \times M$. И как в этом контексте возможно появление повторение дуг без повторения вершин?

 
 
 
 Re: Простой путь в графе
Сообщение01.09.2012, 23:13 
Аватара пользователя
Unconnected в сообщении #613650 писал(а):
каждая дуга встречается не более одного раза
Может быть, там было слово "вершина"?

 
 
 
 Re: Простой путь в графе
Сообщение01.09.2012, 23:17 
Нет, именно так, как скопировал. Значит, опечатка?
А вот ещё: "Контур - простой путь, в котором начало и конец совпадают". Но в простом пути вершин на 1 больше, чем дуг.. а в контуре, выходит, одинаково. Как так?

 
 
 
 Re: Простой путь в графе
Сообщение01.09.2012, 23:52 
Аватара пользователя
Unconnected в сообщении #613658 писал(а):
Нет, именно так как скопировал. Значит, опечатка?
Не обязательно, мой вопрос был задан просто на всякий случай, чтобы Вы уточнили формулировку. Разумеется, повторение дуг без повторения вершин невозможно.
Я посмотрел книжку Ф.Харари "Теория графов", но там терминология несколько отличается от Вашей.
Маршрут - конечная последовательность рёбер графа, в которой начало следующего ребра совпадает с концом предыдущего (фактически там написано иначе, но смысл такой).
Маршрут замкнутый, если начало первого ребра совпадает с концом последнего.
Цепь - это маршрут, в котором все рёбра различны.
Цепь простая (вот здесь в английском тексте используется термин path - путь), если все её вершины различны.
Цикл - замкнутая цепь.
Простой цикл - замкнутый маршрут, в котором все вершины различны, причём, их не меньше трёх.

Unconnected в сообщении #613658 писал(а):
А вот ещё: "Контур - простой путь, в котором начало и конец совпадают". Но в простом пути вершин на 1 больше, чем дуг.. а в контуре, выходит, одинаково. Как так?
Ну, одинаково. Первая и последняя вершины ведь совпадают, поэтому различных на одну меньше.

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


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