Графы

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

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

@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

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

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

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

@Nameless One 5816 / 3468 / 356 Регистрация: 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 5816 / 3468 / 356 Регистрация: 08.02.2010 Сообщений: 7,448
	16.11.2011, 18:44	3
	Вот пример задачи: Дискретная математика 0

@Nameless One 5816 / 3468 / 356 Регистрация: 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 5816 / 3468 / 356 Регистрация: 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

Опции темы