Колесо (теорія графів): відмінності між версіями

[неперевірена версія][неперевірена версія]
Вилучено вміст Додано вміст
м автоматична заміна {{Не перекладено}} вікі-посиланнями на перекладені статті
м автоматична заміна {{Не перекладено}} вікі-посиланнями на перекладені статті
Рядок 57:
У теорії [[Матроїд|матроїдів]] є два особливо важливих види матроїдів&nbsp;— '''колеса''' і '''вихор''', і обидва види є похідними від графів-коліс. Матроїд '''k'''- колеса&nbsp;— це {{не перекладено | Графовий матроїд | графові матроїди ||graphic matroid}}колеса ''W''<sub>''k+1''</sub>, a матроїд '' k ''-вихору виходить з матроїда ''k''-колеса шляхом оголошення зовнішнього циклу (обода) такою ж незалежною множиною, як і її [[Кістякове дерево|кістякове дерево]].
 
Колесо ''W''<sub>6</sub> є прикладом у гіпотезі [[Ердеш Пал|Пол Ердеша]]({{не перекладено|[[Теорія Рамсея|теорії Рамсея||Ramsey theory}}]])&nbsp;— він висловив припущення, що повний граф має найменше число Рамсея серед всіх графів з тим же хроматичним числом. Однак Фаудри і МакКей (Faudree, McKay, 1993) показали, що для ''W''<sub>6</sub> число Рамсея дорівнює 17, в той час як для повного графа ''K''<sub>4</sub>, з тим же хроматичним числом, число Рамсея дорівнює 18.
<ref>{{книга
| автор = Ralph J. Faudree, Brendan D. McKay