Обговорення:Двочастковий граф

Двочастинний/двочастковий/дводольний граф

@Base, NickK, IhorLviv, Vlasenko D та Олюсь: маємо в статтях (навіть у назвах) різнобій термінології. Тут у преамбулі наведено синоніми, але було б краще далі в тесті та в інших статтях використовувати якийсь один варіант. В старих словниках переважає двочастковий, в новіших додається двочастинний, в літературі зустрічається дводольний. Що вибрати? --lxlalexlxl (обговорення) 11:02, 23 квітня 2022 (UTC)

@Lxlalexlxl: Двочастинний — черговий неологізм Мейнаровича, джерел майже нема. У джерелах двочасткового рази в 2,5 менше за дводольний. Я б обрав дводольний, але оскільки так у росіян, можна й двочастковий — NickK (обг.) 11:16, 23 квітня 2022 (UTC)

@Lxlalexlxl: Вітаю! За Вашим посиланням у словнику сказано: 3. мат. двочастковий; Тобто, маємо граф, який складається з двох частин, тому двочастковий. Доля у нас інше означає. --Vlasenko D (обговорення) 11:39, 23 квітня 2022 (UTC)

Граф з однією вершиною

Граф з однією вершиною (звісно, без ребер) не дводольний, проте циклів непарної довжини він не містить. --Spectorsky (обговорення) 20:44, 22 листопада 2023 (UTC)

@Spectorsky: Порівняв з англовікі - було відсутнє слово "неорієнтований". Переніс звідти джерела. В другому джерелі написано: "an undirected graph is bipartite if and only if it has no cycle of odd length". Чи орієнтований граф із однією вершиною? (ChatGPT каже, що так :)) --lxlalexlxl (обговорення) 21:56, 22 листопада 2023 (UTC)

Дякую за відповідь. Я думав про неорієнтований дводольний граф, але питання щодо графу з однією вершиною, здається, залишається і для орграфів. Взагалі, простий граф з однією вершиною взагалі не містить ребер - ані орієнтованих, ані неорієнтованих. --Spectorsky (обговорення) 16:09, 25 листопада 2023 (UTC)

@Spectorsky: Якщо у властивості є слово "неорієнтований", а граф з однієї вершини вважаємо орієнтованим, то проблема з формулюванням властивості зникає. --lxlalexlxl (обговорення) 18:12, 25 листопада 2023 (UTC)

Мабуть, треба дозволити, щоб долі могли бути порожніми (в англійській та російській версіях немає умови непорожності долей). --Spectorsky (обговорення) 17:41, 25 листопада 2023 (UTC)

@Spectorsky: В нас це явно заборонено у визначенні: "дві підмножини $U\cup V=W\quad |U|>0,|V|>0$". --lxlalexlxl (обговорення) 18:18, 25 листопада 2023 (UTC)

Думаю, що це обмеження помилкове (в англійській та російській версіях долі можуть бути непорожніми). Якщо ж вимагати, щоб долі були непорожніми, треба заборонити одновершинні графи у лемі Кеніга. --Spectorsky (обговорення) 18:22, 25 листопада 2023 (UTC)

Очепятка: в англійській та російській версіях долі можуть бути непорожніми --Spectorsky (обговорення) 18:30, 25 листопада 2023 (UTC)

@Spectorsky та IhorLviv: Обмеження в українській існує з першої редакції статті. Пройшло 15 років, але може @IhorLviv щось підкаже про джерело? --lxlalexlxl (обговорення) 19:26, 25 листопада 2023 (UTC)

Можливо, бувають різні варіації означень. але тоді треба виправити формулювання леми Кеніга (властивість "Неорієнтований граф є двочастковим тоді й лише тоді, коли він не містить циклів непарної довжини"), заборонивши там одновершинні графи. --Spectorsky (обговорення) 19:54, 25 листопада 2023 (UTC)

@Spectorsky: Якщо одновершинний граф орієнтований, то на нього ця властивість не поширюється. --lxlalexlxl (обговорення) 19:59, 25 листопада 2023 (UTC)

@lxlalexlxl Простий одновершинний граф є порожнім, тобто не містить ребер. На що може вплинути орієнтація того, чого немає?

Врешті-решт, як бути з одновершинним неорієнтованим графом? Або у згаданій лемі Кеніга забороняти випадок однієї вершин, або дозволяти порожні долі. Я схиляюсь до другого варіанта (треба подивитись кілька авторитетних джерел). Але так, як зараз, залишати не можна. --Spectorsky (обговорення) 20:44, 25 листопада 2023 (UTC)

@Spectorsky: Треба з'ясувати, як авторитетні джерела "ставляться" до одновершинного графа, тобто, чи є домовленість вважати його орієнтованим. --lxlalexlxl (обговорення) 20:51, 25 листопада 2023 (UTC)

@Spectorsky: Наприклад, тут є зображення орієнтованого графа з трьома вершинами, в якому немає дуг. Тобто, граф без дуг вважається орієнтованим. --lxlalexlxl (обговорення) 20:57, 25 листопада 2023 (UTC)

Знайшов таке визначення: "Орієнтованим графом G=(V,E) називають сукупність двох множин — непорожньої множини вершин V і множини орієнтованих ребер (дуг) E". Тобто, множина дуг орієнтованого графа може бути порожньою, що й маємо в одновершинного графа. --lxlalexlxl (обговорення) 21:02, 25 листопада 2023 (UTC)

Гаразд. Розглянемо неорієнтований одновершинний граф. Згідно з наявним означенням він не є дводольним, однак непарних циклів (як і будь-яких інших) там немає. --Spectorsky (обговорення) 22:25, 25 листопада 2023 (UTC)

@Spectorsky: Виходячи з процитованого визначення, одновершинного неорієнтованого графа не існує: непорожня множина вершин + порожня множина дуг = орієнтований граф. --lxlalexlxl (обговорення) 08:00, 26 листопада 2023 (UTC)

@Lxlalexlxl Згідно з означенням неорієнтованого графу (відсутність орієнтації ребер), порожній граф є неорієнтованим. Насправді, порожній граф є як орієнтованим, так і неорієнтованим, бо ребра відсутні - формально кожне ребро порожнього графу (!!) є як орієнтованим, так і неорієнтованим. --Spectorsky (обговорення) 09:16, 26 листопада 2023 (UTC)

Ми обговорюємо щось, суміжне з парністю нуля. Тут діють домовленості, які спрощують подальші маніпуляції. Потрібно прийняти щось одне:

• граф без дуг орієнтований;
• граф без дуг не орієнтований;
• граф без дуг такий, як нам зручно.

Тільки після вибору одного з варіантів буде зрозуміло, про що говорити далі. --lxlalexlxl (обговорення) 13:28, 26 листопада 2023 (UTC)

@Lxlalexlxl 0 - парне число, без додаткових домовленостей! --Spectorsky (обговорення) 14:24, 26 листопада 2023 (UTC)

@Spectorsky: Так, нуль - число парне. Але тільки цій проблемі присвячено окрему статтю, яка в декількох мовних розділах вікіпедії є вибраною. При цьому парність числа 8 питань не викликає. Граф із однією вершиною - орієнтований. Чому вважати так зручніше - треба думати. --lxlalexlxl (обговорення) 14:37, 26 листопада 2023 (UTC)