Что значат цифры в скобках после G

@Nuyta · Регистрация: 14.11.2020

Author24 — интернет-сервис помощи студентам

Задача: Вершинами графа G(n, 3, 1) являются двоичные вектора (x1, x2, . . . , xn), такие что x1+x2+. . .+xn =
3. Два вектора смежны, если их скалярное произведение равно 1. Постройте графы G(4, 3, 1) и
G(5, 3, 1).

Вопрос чрезвычайно глуп, но что значат цифры в скобках после G?
Сначала мне показалось что количество вершин + количество рёбер, но тогда последняя цифра - что? Ведь определение гласит - граф это пара G(V,E), где V - непустое множество вершин, а E - непустое множество рёбер.

@mihailm · 10.08.2021, 21:03

Сообщение от Nuyta

Вопрос чрезвычайно глуп, но что значат цифры в скобках после G?

количество координат у вершин, сумма координат у каждой вершины и наверное условие смежности вершин (величина скалярного произведения).

Сообщение от Nuyta

G(V,E)

Это никак не связано с

Сообщение от Nuyta

G(4, 3, 1)

@3D Homer · 10.08.2021, 22:43

Сообщение от Nuyta

Вопрос чрезвычайно глуп, но что значат цифры в скобках после G?

Формулировка задачи и этот вопрос похожи на следующее. Дано: капибара — это самый крупный среди современных грызунов. Вопрос: но что же такое капибара?

Фраза "Вершинами графа G(n, 3, 1) являются двоичные вектора..." — это определение. Его можно переформулировать следующим образом: "G(n, 3, 1) — это граф, вершинами которого являются двоичные вектора...". После этого, очевидно, спрашивать, что такое G(n, 3, 1), не имеет смысла. Я согласен с mihailm о смысле аргументов 3 и 1, но это даже не важно. Автор задачи имеет право обозначить интересующий его объект как угодно, хоть Щ(n, 31Ф). С другой стороны смысл аргумента n ясен из формулировки: это длина векторов. Поэтому ясно, что такое G(4, 3, 1) — это объект, определение которого получается из приведенного определения подстановкой 4 вместо n.

Байт · 11.08.2021, 11:27

Nuyta, Я надеюсь, объяснения предыдущих ораторов вам понятны?
Даже я, кажется, понял

А графы будут такими
G(4,3,1) состоит из 4-х вершин
(0 1 1 1)
(1 0 1 1)
(1 1 0 1)
(1 1 1 0)
Ребер нет
G(5, 3, 1) состоит из 10-ти вершин(
Выписывать их мне стало скучно. Если задача вами еще не решена - давайте вместе
Смежные есть. Например (1 1 0 0 1) и (0 0 1 1 1)
Легко увидеть, что каждая вершина смежна с 3-мя другими
...
А определение.... Видимо, потом пойдут графы G(n, m, k)
Скорее всего, это связано с кодированиями....

@Nuyta · 14.08.2021, 21:36 **[ТС]**

Байт, на самом деле, всё ещё не решила. Давайте вместе, если несложно Вам. Я не совсем поняла из Ваших суждений, почему в графе 5,3,1 получилось 10 вершин. Я новичок в дискретной математике, так что уж простите за глупые вопросы((
Если можно, покажите на рисунках, совсем не понимаю..

@3D Homer · 14.08.2021, 21:41

Сообщение от Nuyta

Я не совсем поняла из Ваших суждений, почему в графе 5,3,1 получилось 10 вершин.

Не Байт, но: попробуйте систематически выписать все вершины, то есть двоичные векторы длины 5 с тремя единицами и двумя нулями. Также полезно вспомнить формулу для числа сочетаний. В качестве множества, из которого берутся эти сочетания, рассматривается множество мест в векторе, то есть {1, 2, 3, 4, 5}.

@Nuyta · 14.08.2021, 21:46 **[ТС]**

3D Homer, так-с, я ещё раз извиняюсь, но.. Ок, откуда вы цифры такие берёте? Я совсем глупой себя ощущаю, но искренне не понимаю. Ладно 5 длина, там оно есть. Откуда три единицы и два нуля? Кстати у меня при выписывании только 7 вариаций получилось

@3D Homer · 14.08.2021, 21:59

Сообщение от Nuyta

Откуда три единицы и два нуля?

Тогда встречный вопрос: почему вы пытаетесь решить задачу, не поняв ключевое определение? Если в условии что-то непонятно, нужно задавать вопросы, пока это не станет понятно.

С учетом моего замечания в сообщении 3 определение можно сформулировать так: "G(n, 3, 1) — это граф, вершинами которого являются двоичные вектора (x1, x2, . . . , xn), такие что x1+x2+. . .+xn = 3. Два вектора смежны, если их скалярное произведение равно 1". В частности, подставляя 5 вместо n, получаем: "G(5, 3, 1) — это граф, вершинами которого являются двоичные вектора (x1, x2, x3, x4, x5), такие что x1 + x2 + x3 + x4 + x5 = 3". Насколько я понимаю, двоичный вектор — это упорядоченная последовательность 0 и 1. Раз сумма должна быть равна 3, значит, в векторе ровно 3 единицы, а остальные нули. Понятно?

Сообщение от Nuyta

Кстати у меня при выписывании только 7 вариаций получилось

Напишите их, только желательно в некотором систематическом порядке, который позволил бы ничего не пропустить.

@Nuyta · 14.08.2021, 22:13 **[ТС]**

3D Homer, ах, вот оно что!!
Господи, теперь понятно про условие, благодарствую!
По поводу векторов:

11100
01110
00111
10011
11001
10101
10110

Может глуплю, но я вроде не пропустила.

Добавлено через 10 минут
3D Homer, кстати, не подскажете, как по этим векторам понять смежность? Совсем не шарю.

Сообщение от 3D Homer

формулу для числа сочетаний

И что за штука?)

@3D Homer · 14.08.2021, 22:23

Вот все векторы.

Код

Их количество равно числу способов выбрать места для двух нулей из 5 возможных мест.

Добавлено через 4 минуты

Сообщение от Nuyta

как по этим векторам понять смежность?

Сообщение от 3D Homer

Два вектора смежны, если их скалярное произведение равно 1

Напишите, что вам непонятно в этой фразе.

Сообщение от Nuyta

И что за штука?

См. Википедию или учебник. Было бы немного странно, если бы вы перед теорией графов не проходили основные понятия комбинаторики. Но, впрочем, это необязательно.

@Nuyta · 14.08.2021, 22:32 **[ТС]**

3D Homer, да-да, комбинаторика была. Я не до конца её усвоила и что-то уже забылось. Навёрстываю графы.

А, я про скалярное произведение не учла.
Как это работает? Вот допустим два вектора: 11100 и 00111, как их скалярное получить? Там же a*b*cos

((

@3D Homer · 14.08.2021, 22:38

Сообщение от Nuyta

Вот допустим два вектора: 11100 и 00111, как их скалярное получить? Там же a*b*cos

Имеется в виду эта формула.

@Nuyta · 14.08.2021, 22:42 **[ТС]**

3D Homer, аааа.. Ну, в общем-то, понятно. Огромное спасибо Вам, что внесли немного ясности в мои знания дискретной математики..)
Зная комбинаторику, посмотреть и построить это можно куда быстрее, а так просто втупую подсчитывать нужно, верно ?

@3D Homer · 14.08.2021, 23:49

Сообщение от Nuyta

Зная комбинаторику, посмотреть и построить это можно куда быстрее

С помощью комбинаторики можно посчитать количество ребер, но я не уверен, как найти множество самих ребер.

Впрочем, легко понять, что это кубический граф, то есть степень каждой вершины равна 3. Действительно, рассмотрим. например, вершину 11100. В смежной вершине напротив двух нулей должны стоять единицы: только тогда в каждом разряде, кроме одного, напротив нуля будет стоять единица и, таким образом, скалярное произведение будет 1. Поэтому нужно выбрать, напротив какой из единиц первой вершины будет стоять единица (а не нуль) второй. Так, вершине 11100 будут смежны 10011, 01011 и 00111.

Граф будет следующим. Оказывается, это граф Петерсена.

@3D Homer $Эксперт по математике/физике$ 4952 / 3570 / 1151 Регистрация: 01.09.2014 Сообщений: 9,661
	14.08.2021, 22:38	12
	Сообщение от Nuyta Вот допустим два вектора: 11100 и 00111, как их скалярное получить? Там же abcos Имеется в виду эта формула. 0

@Nuyta 14 / 11 / 4 Регистрация: 14.11.2020 Сообщений: 411
		1
	Что значат цифры в скобках после G 10.08.2021, 19:29. Показов 1210. Ответов 13 Метки нет (Все метки) Задача: Вершинами графа G(n, 3, 1) являются двоичные вектора (x1, x2, . . . , xn), такие что x1+x2+. . .+xn = 3. Два вектора смежны, если их скалярное произведение равно 1. Постройте графы G(4, 3, 1) и G(5, 3, 1). Вопрос чрезвычайно глуп, но что значат цифры в скобках после G? Сначала мне показалось что количество вершин + количество рёбер, но тогда последняя цифра - что? Ведь определение гласит - граф это пара G(V,E), где V - непустое множество вершин, а E - непустое множество рёбер. 0

@mihailm 1590 / 1040 / 278 Регистрация: 05.10.2014 Сообщений: 5,123
	10.08.2021, 21:03	2
	Сообщение от Nuyta Вопрос чрезвычайно глуп, но что значат цифры в скобках после G? количество координат у вершин, сумма координат у каждой вершины и наверное условие смежности вершин (величина скалярного произведения). Сообщение от Nuyta G(V,E) Это никак не связано с Сообщение от Nuyta G(4, 3, 1) 0

@3D Homer $Эксперт по математике/физике$ 4952 / 3570 / 1151 Регистрация: 01.09.2014 Сообщений: 9,661
	10.08.2021, 22:43	3
	Сообщение от Nuyta Вопрос чрезвычайно глуп, но что значат цифры в скобках после G? Формулировка задачи и этот вопрос похожи на следующее. Дано: капибара — это самый крупный среди современных грызунов. Вопрос: но что же такое капибара? Фраза "Вершинами графа G(n, 3, 1) являются двоичные вектора..." — это определение. Его можно переформулировать следующим образом: "G(n, 3, 1) — это граф, вершинами которого являются двоичные вектора...". После этого, очевидно, спрашивать, что такое G(n, 3, 1), не имеет смысла. Я согласен с mihailm о смысле аргументов 3 и 1, но это даже не важно. Автор задачи имеет право обозначить интересующий его объект как угодно, хоть Щ(n, 31Ф). С другой стороны смысл аргумента n ясен из формулировки: это длина векторов. Поэтому ясно, что такое G(4, 3, 1) — это объект, определение которого получается из приведенного определения подстановкой 4 вместо n. 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	11.08.2021, 11:27	4
	Nuyta, Я надеюсь, объяснения предыдущих ораторов вам понятны? Даже я, кажется, понял А графы будут такими G(4,3,1) состоит из 4-х вершин (0 1 1 1) (1 0 1 1) (1 1 0 1) (1 1 1 0) Ребер нет G(5, 3, 1) состоит из 10-ти вершин( Выписывать их мне стало скучно. Если задача вами еще не решена - давайте вместе Смежные есть. Например (1 1 0 0 1) и (0 0 1 1 1) Легко увидеть, что каждая вершина смежна с 3-мя другими ... А определение.... Видимо, потом пойдут графы G(n, m, k) Скорее всего, это связано с кодированиями.... 0

@Nuyta 14 / 11 / 4 Регистрация: 14.11.2020 Сообщений: 411
	14.08.2021, 21:36 [ТС]	5
	Байт, на самом деле, всё ещё не решила. Давайте вместе, если несложно Вам. Я не совсем поняла из Ваших суждений, почему в графе 5,3,1 получилось 10 вершин. Я новичок в дискретной математике, так что уж простите за глупые вопросы(( Если можно, покажите на рисунках, совсем не понимаю.. 0

@3D Homer $Эксперт по математике/физике$ 4952 / 3570 / 1151 Регистрация: 01.09.2014 Сообщений: 9,661
	14.08.2021, 21:41	6
	Сообщение от Nuyta Я не совсем поняла из Ваших суждений, почему в графе 5,3,1 получилось 10 вершин. Не Байт, но: попробуйте систематически выписать все вершины, то есть двоичные векторы длины 5 с тремя единицами и двумя нулями. Также полезно вспомнить формулу для числа сочетаний. В качестве множества, из которого берутся эти сочетания, рассматривается множество мест в векторе, то есть {1, 2, 3, 4, 5}. 1

@Nuyta 14 / 11 / 4 Регистрация: 14.11.2020 Сообщений: 411
	14.08.2021, 21:46 [ТС]	7
	3D Homer, так-с, я ещё раз извиняюсь, но.. Ок, откуда вы цифры такие берёте? Я совсем глупой себя ощущаю, но искренне не понимаю. Ладно 5 длина, там оно есть. Откуда три единицы и два нуля? Кстати у меня при выписывании только 7 вариаций получилось 0

@3D Homer $Эксперт по математике/физике$ 4952 / 3570 / 1151 Регистрация: 01.09.2014 Сообщений: 9,661
	14.08.2021, 21:59	8
	Сообщение от Nuyta Откуда три единицы и два нуля? Тогда встречный вопрос: почему вы пытаетесь решить задачу, не поняв ключевое определение? Если в условии что-то непонятно, нужно задавать вопросы, пока это не станет понятно. С учетом моего замечания в сообщении 3 определение можно сформулировать так: "G(n, 3, 1) — это граф, вершинами которого являются двоичные вектора (x1, x2, . . . , xn), такие что x1+x2+. . .+xn = 3. Два вектора смежны, если их скалярное произведение равно 1". В частности, подставляя 5 вместо n, получаем: "G(5, 3, 1) — это граф, вершинами которого являются двоичные вектора (x1, x2, x3, x4, x5), такие что x1 + x2 + x3 + x4 + x5 = 3". Насколько я понимаю, двоичный вектор — это упорядоченная последовательность 0 и 1. Раз сумма должна быть равна 3, значит, в векторе ровно 3 единицы, а остальные нули. Понятно? Сообщение от Nuyta Кстати у меня при выписывании только 7 вариаций получилось Напишите их, только желательно в некотором систематическом порядке, который позволил бы ничего не пропустить. 0

@Nuyta 14 / 11 / 4 Регистрация: 14.11.2020 Сообщений: 411
	14.08.2021, 22:13 [ТС]	9
	3D Homer, ах, вот оно что!! Господи, теперь понятно про условие, благодарствую! По поводу векторов: 11100 01110 00111 10011 11001 10101 10110 Может глуплю, но я вроде не пропустила. Добавлено через 10 минут 3D Homer, кстати, не подскажете, как по этим векторам понять смежность? Совсем не шарю. Сообщение от 3D Homer формулу для числа сочетаний И что за штука?) 0

@3D Homer $Эксперт по математике/физике$ 4952 / 3570 / 1151 Регистрация: 01.09.2014 Сообщений: 9,661
	14.08.2021, 22:23	10
	Вот все векторы. Код 11100 11010 11001 10110 10101 10011 01110 01101 01011 00111 Их количество равно числу способов выбрать места для двух нулей из 5 возможных мест. Добавлено через 4 минуты Сообщение от Nuyta как по этим векторам понять смежность? Сообщение от 3D Homer Два вектора смежны, если их скалярное произведение равно 1 Напишите, что вам непонятно в этой фразе. Сообщение от Nuyta И что за штука? См. Википедию или учебник. Было бы немного странно, если бы вы перед теорией графов не проходили основные понятия комбинаторики. Но, впрочем, это необязательно. 1

	14.08.2021, 23:49

@Nuyta 14 / 11 / 4 Регистрация: 14.11.2020 Сообщений: 411
	14.08.2021, 22:32 [ТС]	11
	3D Homer, да-да, комбинаторика была. Я не до конца её усвоила и что-то уже забылось. Навёрстываю графы. А, я про скалярное произведение не учла. Как это работает? Вот допустим два вектора: 11100 и 00111, как их скалярное получить? Там же abcos (( 0

@Nuyta 14 / 11 / 4 Регистрация: 14.11.2020 Сообщений: 411
	14.08.2021, 22:42 [ТС]	13
	3D Homer, аааа.. Ну, в общем-то, понятно. Огромное спасибо Вам, что внесли немного ясности в мои знания дискретной математики..) Зная комбинаторику, посмотреть и построить это можно куда быстрее, а так просто втупую подсчитывать нужно, верно ? 0

@3D Homer $Эксперт по математике/физике$ 4952 / 3570 / 1151 Регистрация: 01.09.2014 Сообщений: 9,661
	14.08.2021, 23:49	14
	Сообщение от Nuyta Зная комбинаторику, посмотреть и построить это можно куда быстрее С помощью комбинаторики можно посчитать количество ребер, но я не уверен, как найти множество самих ребер. Впрочем, легко понять, что это кубический граф, то есть степень каждой вершины равна 3. Действительно, рассмотрим. например, вершину 11100. В смежной вершине напротив двух нулей должны стоять единицы: только тогда в каждом разряде, кроме одного, напротив нуля будет стоять единица и, таким образом, скалярное произведение будет 1. Поэтому нужно выбрать, напротив какой из единиц первой вершины будет стоять единица (а не нуль) второй. Так, вершине 11100 будут смежны 10011, 01011 и 00111. Граф будет следующим. Оказывается, это граф Петерсена. 1