Графы. Теоретическое знакомство (первые начинания)

Опубликовано 12.12.2012 | Автор: admin

Тема графов — это интересная, полезная и пугающая тема. Теория графов — "Ужас студента". Алгоритмы на графах — потрясающий ум людей их открывших.

Что такое граф? Чтобы ответить на этот вопрос своим читателям, я буду описывать тему немного по-своему.
Граф — это множество объектов.
В большинстве задач это однотипные объекты. (Множество городов или множество домов, или множество людей, или множество чего-то ещё однотипного)

Чтобы решать задачи с таким множеством, нужно каждый объект из этого множества обозначить как что-то. Общепринято это самое что-то называть вершинами графа.

Описывать графы и основные определения удобно рисунками, поэтому для чтения этой страницы рисунки должны быть включены.

Показать текст общего представления графов

Графы

Показать текст

Графы

Показать текст

Графы

E обычно называют пару вершин. В двумерном массиве этой пароя часто выступают номер строки + номер столбца. По номеру строки и номеру столбца проверяют соединение, и если оно есть на пересечении, то это обозначают в значениях массива (матрицы) в месте пересечения строки и столбца

Показать текст

Графы

Показать текст

Графы

Показать текст

Графы

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

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

У графа могут быть два маршрута или более, которые начинаются в одной и той же вершине и заканчиваются в другой, но оба маршрута заканчиваются в одной и той же другой вершине. Рисунок скорее всего хорошо демонстрирует этот момент. Такие маршруты (дуги, ребра) называются кратными.

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

Вы часто будете встречать понятия смежности и инцендентности. На рисунке красным цветом отмечены два ребра, которые идут в одну точку. Такие ребра, как и вышеописанные вершины, тоже называются смежными.

Вы часто будете встречать понятия смежности и инцендентности. Если объекты вершина и вершина однотипны, если объекты дорога и дорога однотипны, то объекты вершина и дорога не очень-то и однотипны, но чтобы обозначить связь вершины и дороги, существует понятие инцендентности. Т.е. это принадлежность вершины графа к маршруту графа, если маршрут принадлежит вершине графа (стыкуется с ней), то маршрут и вершина инцендентны.

Так как в графе может существовать такая вершина, к которой нет маршрутов, то для такой вершины существует понятие — изолированная вершина.

Этот рисунок уже был самым первым. Но для такой ситуации существует определение — нуль-граф.

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

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

Многое не описано, но эта часть информации может быть кому-то поможет.

Рубрика: Без рубрики

Kulululu:

04.02.2014 в 2:16 пп

Thanks

Ответить

un1acker:

03.03.2014 в 10:48 пп

Спасибо большое за краткое и главное понятное объяснение основных понятий связанных с графами!

Аноним:

29.03.2014 в 7:16 дп

как делать БЛЕАТЬ

ministrel:

09.04.2015 в 6:02 пп

Спасибо большое! Хорошая информация!

Artem:

02.05.2015 в 12:51 пп

все очень круто объяснено, спасибо:)

Мария:

27.05.2015 в 3:19 пп

Спасибо за хорошее объяснение!

28.06.2015 в 4:37 пп

 internal class Program
    {
        private static void Main(string[] args)
        {
            Random rand = new Random();

            const int N = 5;

            int[,] matrix = new int[N, N];
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < N; j++)
                {
                    matrix [i,j] = rand.Next(-100, 100);         
            
                   Console.Write( matrix [i,j] + " ");
                }
                Console.WriteLine();
            }

             Console.WriteLine();
             Console.WriteLine();
            for (int i = 0; i < N; i++)
            {
                if (i % 2 == 0)
                {
                    int sum = 0;
                    for (int j = 0; j < N; j++)
                    {
                        sum += matrix[i, j];


                    }
                    Console.WriteLine("Row number " + i + " arithmetical mean: " + sum / N);
                }
            }
 
            Console.ReadLine();
        }
    }