Обсуждение:Дерево (теория графов)

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску


Untitled[править код]

Предлагаю переименовать эту статью с «Дерево» на «Дерево (теория графов)». А в статье «Дерево» сделать ссылки на другие значения термина.

Такое нет смысла делать пока не пояжились другие статьи --Tosha 14:29, 12 июля 2005 (UTC)

Мне кажется, есть. Даже две причины.
  • не придется потом переделывать ссылки на эту статью
  • есть много ссылок, не относящихся к теории графов и они сейчас синие, а должны быть красными
Предлагаю сделать «Дерево (теория графов)» и «Дерево (значения)».
SergV 18:05, 17 июля 2005 (UTC)

Да, ты прав, большинство ссылок не туда. --Tosha 21:44, 22 июля 2005 (UTC)

Интересная ассимптотика числа неизоморфных деревьев. Хорошо бы вставить ссылку на автора. Нет ли получше нижних оценок на число неизоморфных корневых? Олег.

Otter, Ann.Math. 1948 v.49 №3, p.583-99, ссылка из МатЭнциклопедии --Tosha 02:20, 18 сентября 2005 (UTC)

Цитата: "висячая вершина — это вершина степени 1. Листом дерева называется любая его висячая вершина (вместе с соотв. ребром)." В таком случае под определение листа тут подойдет корень, если у него один потомок,а это бред.

Теорема Кэли.[править код]

Тоша, не стоит ли добавить какую-нибудь ссылку (сноской) про теорему Кэли, для более быстрой, нежели "пойти в библиотеку", проверяемости (да и вообще иметь возможность быстро посмотреть, "откуда оно", для потенциального читателя было бы неплохо)? Я навскидку могу вспомнить записки дубнинского курса Бурмана тут, но а) это просто записки лекций и б) сам я их добавить не могу, ибо нахожусь в конфликте интересов: я слишком тесно с этой школой связан. Burivykh 23:13, 28 октября 2009 (UTC)

Посмотрел -- наверное, не стоит: нарушится баланс статьи. А вот если делать отдельную статью (теорема Кэли плюс числа Гурвица плюс многочлены плюс накрытия), тогда, наверное, можно будет и сослаться. Эх. Ещё одно TODO. :) Burivykh 23:16, 28 октября 2009 (UTC)
О, нашёл независимую ссылку. Правда, там по-другому (не через связь с многочленами и накрытиями), но для одного подтверждения этого достаточно, а двух разных взглядов в статье не специально о теореме Кэли не надо. Burivykh 11:33, 29 октября 2009 (UTC)

Иллюстрация к двоичному дереву[править код]

Пример дерева

Коллеги, картинка-иллюстрация была убрана с комментарием, что это не двоичное дерево. Формально, конечно, степень корня ровно 3, а дерево неориентировано — но оно нарисовано так, что его очень естественно ориентировать «сверху вниз», а тогда оно под определение не подпадает. То есть — действительно, лучше эту картинку не использовать. Кто-нибудь может нарисовать более «каноническую» иллюстрацию? --Burivykh 07:00, 23 января 2011 (UTC)

Добавил иллюстрацию из АнглВики. Petrohan 12:03, 23 января 2011 (UTC)

Связанные определения[править код]

Первое определение вступает в противоречие со вторым. """ Степень узла — количество исходящих дуг (или, иначе, количество поддеревьев узла). Концевой узел (лист, терминальная вершина) — узел со степенью 1 (то есть узел, в который ведёт только одно ребро; в случае ориентированного дерева — узел, в который ведёт только одна дуга и не исходит ни одной дуги). """

Во втором следует написать «узел со степенью 0»? 212.122.7.19 17:57, 2 июня 2015 (UTC) Антон

В английской версии статьи: "A leaf is a vertex of degree 1". Частично поправил, про степень вершины. 79.133.114.37 21:34, 16 июля 2015 (UTC) 79.133.114.37 21:20, 16 июля 2015 (UTC)