46 / 15 / 4
Регистрация: 13.03.2013
Сообщений: 302
|
|
1 | |
Связь графов и чисел16.09.2015, 20:25. Показов 1157. Ответов 6
Метки нет (Все метки)
добрый вечер.
Возник такой вопрос, поиски которого веду, но может быть кто-то знает и сможет помочь ускорить поиски. Если взять граф и подсчитать сколько различных графом можно представить в его матрице смежности, то это число . Только среди этих чисел будет куча изоморфных графов. Так вот, есть ли связь между графом и числом более явная? Например, число 0, можно представить в бинарном виде как набор нулей (причём бесконечный, по сути), а если перенести это число на граф - это получится граф, у которого нет рёбер. есть только вершины (несвязный граф). Ну 1 тоже можно представить, хотя не понятно как её расположить, например, в матрице смежности. т.е.. 0 - это а 1 тогда как? ну и разумеется, можно представить полный граф, т.е. все рёбра между всеми вершинами, - это . В какую сторону смотреть по этому вопросу или какие статьи. чтобы почитать по этому вопросу что-то вразумительное?
0
|
16.09.2015, 20:25 | |
Ответы с готовыми решениями:
6
Теорие графов. Композиция двух неор. графов. Почему графов с семью вершинами меньше чем графов с шестью вершинами? Определяет ли связь, в частности современная связь, структуру государственного управления? связь CPU-314SC и WINDOWS где посмотреть обмен данными и вообще связь |
46 / 15 / 4
Регистрация: 13.03.2013
Сообщений: 302
|
|
18.09.2015, 11:50 [ТС] | 3 |
Ну я просто хочу узнать - связь между графом и числом есть? Это для изоморфизма, да.
0
|
2717 / 1771 / 187
Регистрация: 05.06.2011
Сообщений: 5,129
|
|
18.09.2015, 12:47 | 4 |
Связь между чем угодно и числом — есть. Это совершенно точно.
Изоморфизм — взаимно-однозначное отображение, сохраняющее структуру, то бишь, взаимосвязи (отношения) между элементами множеств. Какие именно взаимосвязи ты бы хотел сохранить? Если никакие, ответ достаточно очевиден.
0
|
46 / 15 / 4
Регистрация: 13.03.2013
Сообщений: 302
|
|
18.09.2015, 17:51 [ТС] | 5 |
вопрос вот возник откуда:
нужна была генерация матриц смежности графа, и очевидный вариант был предложен - берём число, перегоняем его в битовое представление, подставляем в матрицу смежности и радуемся (подстановка, например. в верхний треугольник, а нижний отзеркаливаем, числа для ячеек в матрице идёт по порядку сверху вниз слева направо). Но это мы тут на форуме примерно так решили. А ведь по сути те числа можно было по разному расставлять, по сути. по другому матрицу заполнять или что-то ещё. И результат мог бы быть другим, я имею ввиду, что битовую цепочку числа 7 (111), забито или справа или слева "0" можно было разместить в матрице по-разному, и эти отображения графа могли выглядеть по разному (не проверяла ещё этот вопрос). Типа так: или так: Так вот, если ли какое-то чёткое понятие, что граф. который может быть построен от битового значения 8 выглядит так и только так (и тут типа граф на "числе 8"). Мысль вопроса поняли? кстати, графы получились разными - первый это дерево, второй несвязный с циклом.
0
|
2717 / 1771 / 187
Регистрация: 05.06.2011
Сообщений: 5,129
|
|
19.09.2015, 04:12 | 6 |
Сообщение было отмечено Nullik как решение
Решение
Хм, ну, примерно понял.
Если вопрос в том, чтобы перечислить все графы определённого порядка, то да, примерно так. Только семёрка будет не 111, а 000111 — нам же надо перечислить 6 бит. Правило расстановки бит числа по матрице могут быть любыми и никакого наиболее естественного среди них нет. Ну и, повторюсь, задача установления, изоморфны графы или нет, насколько я помню — в принципе очень сложная. То бишь, чего-то сильно быстрее перебора всех возможных соответствий и проверки изоморфизма нет. Вот, например, для начала может подойти
1
|
46 / 15 / 4
Регистрация: 13.03.2013
Сообщений: 302
|
|
27.09.2015, 22:07 [ТС] | 7 |
ну примерно так и выходит. Сам задаёшь "тип счисления" для матрицы, а про 7 верно, тоже потом заметила\подправила (у себя). Спасибо!
0
|
27.09.2015, 22:07 | |
27.09.2015, 22:07 | |
Помогаю со студенческими работами здесь
7
Создать любые две таблицы, установить между ними связь, и с помощью запроса показать эту связь Связь чисел Фибоначчи и числа "сочетаний" объединение графов Построение графов Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |