Графы

@Zhandarbek · Регистрация: 15.08.2011

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

Всем привет! Пишу в принципе год, но с графами не сталкивался, поэтому нужна помощь. Вообщем вопросы, интересующие меня: что есть граф и с чем его едят?, и реализация на С++, и пример како-нить задачи. Заранее спасибо

@Nameless One · 16.11.2011, 18:43

Zhandarbek, граф - это пара $https://www.cyberforum.ru/cgi-bin/latex.cgi?(V, \, E)$ , где $https://www.cyberforum.ru/cgi-bin/latex.cgi?V$ - называется множеством вершин, а $https://www.cyberforum.ru/cgi-bin/latex.cgi?E \subseteq V \times V$ - множество ребер графа. $https://www.cyberforum.ru/cgi-bin/latex.cgi?(\forall v_1, \, v_2 \in V) (v_1, v_2) \in E$ , если и только если вершины $https://www.cyberforum.ru/cgi-bin/latex.cgi?v_1$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?v_2$ соединены ребром. Граф можно представлять в виде т.н. "матрицы смежности", где элемент с индексами (i, j) не равен нулю, если i-тую и j-тую вершину соединяет ребро. А про то, что графы бывают ориентированные и неориентированные, и много другого интересного ты сможешь узнать, если не поленишься и откроешь учебник по дискретке или на крайний случай прочитаешь соответствующую статью в википедии

@Nameless One · 16.11.2011, 18:44

Вот пример задачи: Дискретная математика

@amor1k · 16.11.2011, 19:00

простая реализация матрицы смежности))

C++

for(int i=0;i<n;i++)
{
    a[i][i] = 0;
    for(int j=i+1;j<n;j++)
    {
        cout<<"a["<<i+1<<"]["<<j+1<<"] = ";
        cin>>a[i][j];
        a[j][i] = a[i][j];
    }
}

@Nameless One · 16.11.2011, 19:08

amor1k, а вершина разве не может быть соединена сама с собой?

@amor1k · 16.11.2011, 19:13

ну это пример неориентированного безпетельного графа)

@Zhandarbek · 16.11.2011, 19:27 **[ТС]**

а разве слово " неориентированный граф" не означает, что он безпетельный??

@Nameless One · 16.11.2011, 19:29

Zhandarbek, нет, не означает. Это разные понятия

@Zhandarbek · 16.11.2011, 19:31 **[ТС]**

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

Евгений М. · 16.11.2011, 19:57

Zhandarbek, все-таки:

Сообщение от Nameless One

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

@Рулик · 16.11.2011, 20:04

Дали лабораторную и теорию.

Евгений М. 1080 / 1007 / 106 Регистрация: 28.02.2010 Сообщений: 2,889
	16.11.2011, 19:57	10
	Zhandarbek, все-таки: Сообщение от Nameless One много другого интересного ты сможешь узнать, если не поленишься и откроешь учебник по дискретке или на крайний случай прочитаешь соответствующую статью в википедии 0

Новые блоги и статьи
Элементы алгоритмизации hw_wired 28.01.2025 Основы алгоритмизации В современном мире алгоритмы играют фундаментальную роль в развитии информационных технологий и программирования. Понимание основ алгоритмизации является ключевым элементом в. . .	Человек и информация hw_wired 28.01.2025 Введение: роль информации в познании мира В современном мире информация играет фундаментальную роль в процессе познания окружающей действительности. Она представляет собой совокупность сведений об. . .	Компьютер и информация hw_wired 28.01.2025 Эволюция вычислительных машин История развития вычислительной техники начинается задолго до появления первых электронных устройств. Человечество всегда стремилось упростить процесс вычислений и. . .	Информационные технологии hw_wired 28.01.2025 Введение в современные технологии работы с информацией В современном мире информационные технологии стали неотъемлемой частью практически всех сфер человеческой деятельности. Они существенно. . .	Информация вокруг нас hw_wired 28.01.2025 Основные понятия информации В современном мире понятие информации является фундаментальным и охватывает практически все сферы человеческой деятельности. Информация представляет собой совокупность. . .	Компьютер для начинающих hw_wired 28.01.2025 Введение в мир компьютерных технологий В современном мире информация стала одним из важнейших ресурсов человечества, определяющим развитие общества и технологий. Наша жизнь неразрывно связана с. . .
[golang] 189. Rotate Array alhaos 28.01.2025 Повороты рукоятки, целочисленный слайс нужно сдвинуть на целое положительное число. Мне очень нравится решение на GO / / https:/ / leetcode. com/ studyplan/ top-interview-150/ package topInterview . . .	КуМир: решение задач на матрицы bytestream 28.01.2025 КуМир представляет собой среду для обучения программированию, которая включает в себя мощные инструменты для работы с матрицами. Матрица в программировании - это двумерный массив, состоящий из. . .	КуМир: решение задач на строки bytestream 28.01.2025 В системе программирования КуМир работа со строковыми данными является одним из важнейших аспектов создания программ. Строки представляют собой последовательности символов, заключенные в кавычки,. . .	КуМир: решение геометрических задач bytestream 28.01.2025 Программирование геометрических задач в среде КуМир становится всё более актуальным в обучении школьников и студентов. КуМир — это разработанная в России обучающая программная среда, предназначенная. . .	КуМир, исполнитель Водолей: Задачи и решения bytestream 28.01.2025 КуМир — это образовательная среда для обучения программированию. Она предлагает пользователям разнообразные инструменты для разработки и отладки программ, что особенно ценно для студентов и. . .	КуМир, исполнитель Чертежник: Решение задач bytestream 28.01.2025 КуМир (Комплект Учебных МИРов) представляет собой образовательную среду для обучения основам программирования и алгоритмизации. Исполнитель Чертежник работает на координатной плоскости, где может. . .

@Zhandarbek 3 / 3 / 0 Регистрация: 15.08.2011 Сообщений: 60
		1
	Графы 16.11.2011, 18:36. Показов 2227. Ответов 10 Метки нет (Все метки) Всем привет! Пишу в принципе год, но с графами не сталкивался, поэтому нужна помощь. Вообщем вопросы, интересующие меня: что есть граф и с чем его едят?, и реализация на С++, и пример како-нить задачи. Заранее спасибо 0

@Nameless One 5828 / 3479 / 358 Регистрация: 08.02.2010 Сообщений: 7,448
	16.11.2011, 18:43	2
	Zhandarbek, граф - это пара $https://www.cyberforum.ru/cgi-bin/latex.cgi?(V, \, E)$ , где $https://www.cyberforum.ru/cgi-bin/latex.cgi?V$ - называется множеством вершин, а $https://www.cyberforum.ru/cgi-bin/latex.cgi?E \subseteq V \times V$ - множество ребер графа. $https://www.cyberforum.ru/cgi-bin/latex.cgi?(\forall v_1, \, v_2 \in V) (v_1, v_2) \in E$ , если и только если вершины $https://www.cyberforum.ru/cgi-bin/latex.cgi?v_1$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?v_2$ соединены ребром. Граф можно представлять в виде т.н. "матрицы смежности", где элемент с индексами (i, j) не равен нулю, если i-тую и j-тую вершину соединяет ребро. А про то, что графы бывают ориентированные и неориентированные, и много другого интересного ты сможешь узнать, если не поленишься и откроешь учебник по дискретке или на крайний случай прочитаешь соответствующую статью в википедии 0

@Nameless One 5828 / 3479 / 358 Регистрация: 08.02.2010 Сообщений: 7,448
	16.11.2011, 18:44	3
	Вот пример задачи: Дискретная математика 0

@Nameless One 5828 / 3479 / 358 Регистрация: 08.02.2010 Сообщений: 7,448
	16.11.2011, 19:08	5
	amor1k, а вершина разве не может быть соединена сама с собой? 0

@amor1k Студент 148 / 148 / 64 Регистрация: 18.01.2011 Сообщений: 469
	16.11.2011, 19:13	6
	ну это пример неориентированного безпетельного графа) 0

@Zhandarbek 3 / 3 / 0 Регистрация: 15.08.2011 Сообщений: 60
	16.11.2011, 19:27 [ТС]	7
	а разве слово " неориентированный граф" не означает, что он безпетельный?? 0

@Nameless One 5828 / 3479 / 358 Регистрация: 08.02.2010 Сообщений: 7,448
	16.11.2011, 19:29	8
	Zhandarbek, нет, не означает. Это разные понятия 0

@Zhandarbek 3 / 3 / 0 Регистрация: 15.08.2011 Сообщений: 60
	16.11.2011, 19:31 [ТС]	9
	Странно, почему-то мне всегда казалось, что петли только в ориентированном графе... хотя вам виднее, у вас больше опыта 0

@Рулик 8 / 8 / 2 Регистрация: 14.11.2011 Сообщений: 54
	16.11.2011, 20:04	11
	Дали лабораторную и теорию. 0