Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/15: Рейтинг темы: голосов - 15, средняя оценка - 4.67
0 / 0 / 0
Регистрация: 08.01.2017
Сообщений: 39
Записей в блоге: 1
1

Найти эйлерову цепь или эйлеров цикл в графе

04.06.2017, 13:59. Показов 2835. Ответов 1
Метки нет (Все метки)

Найти эйлерову цепь или эйлеров цикл в графе
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
04.06.2017, 13:59
Ответы с готовыми решениями:

Построить эйлерову цепь в графе.
Всем доброго времени суток! Помогите пожалуйста или подскажите как сделать следующее. Дали задание...

Эйлеров цикл и цепь
1) Найти эйлеров граф и указать в нем эйлеров цикл (нумерацией ребер) Вроде как первый, т.к....

Определите, содержит ли граф G, представленный на рисунке, эйлерову цепь
Определите, содержит ли граф G, представленный на рисунке, эйлерову цепь

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

1
0 / 0 / 0
Регистрация: 05.05.2017
Сообщений: 7
Записей в блоге: 2
25.03.2019, 20:57 2
На данный момент пишу эту программу. Только на c#. Ниже представлен код для поиска цикла в матрице смежности из текстового файла, где 1 строка - число вершин n, а ниже - матрица смежности.

Не спорю, есть костыли и т.д. Кому интересно более подробное разъяснение - стучите в лс.
Алгоритм:

Кликните здесь для просмотра всего текста
stack St;
в St кладём любую вершину (стартовая вершина);
пока St не пустой
пусть V - значение на вершине St;
если степень(V) = 0, то
добавляем V к ответу;
снимаем V с вершины St;
иначе
находим любое ребро, выходящее из V;
удаляем его из графа;
Также я минусовал степени вершин и убирал смежности вершин в матрице matrix в
второй конец этого ребра кладём в St;

Программа:
Кликните здесь для просмотра всего текста
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
 
namespace Эйлер.Индивидуалка
{
    class Program
    {
        static int Smezh(int [,]matrix, int a,int n)
        {
            int k = 0;
            for(int j=0;j<n;j++)
            {
                if (matrix[a, j] == 1) k++;
            }
            return k;
        }
 
        static void Main()
        {
            int nechet = 0; //показывает в графе кол-во нечетных вершин
            var stack = new Stack<int>();
            string[] Mass = File.ReadAllLines(@"D:\DEBUG.txt", System.Text.Encoding.Default); //
            int n = Convert.ToInt32(Mass[0]);
            int[,] a = new int[n, n];
            for (int i = 0; i < Mass.Length; i++)
            {
 
                Console.WriteLine("{0,5}", Mass[i]);
                
            }
            int[,] matrix = new int[n, n];
            for (int p = 0; p < n; p++)
            {
                //удаляю пробелы и заножу символ как число в массив m
                int[] m = Mass[p + 1].Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(s => int.Parse(s)).ToArray();
                for (int i = 0; i < m.Length; i++)
                {
                    matrix[p, i] = m[i]; //добавляю это число в двумерный массив
                }
            }
            Console.WriteLine("Матрица:");
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    Console.Write("{0,5}",matrix[i, j]);
                }
                Console.WriteLine(" ");
            }
            int otvet_k = 0; //счетчик для добавления цепи
            var otvet = new Stack<int>();
            int[] v = new int[n]; //вершина-степень
            int[,] v_i = new int[n, n]; // вершина - другие вершины (проверка на смежность)
            int smezhnost = 0; // параметр для проверки на смежность вершин, т.е. если нарушена матрица, то =1 и вывод ошибки
            for (int i = 0; i < n; i++)
            { 
                for(int j=0;j<n;j++)
                {
                    if (matrix[i, j] == matrix[j, i]) //проверяю матрицу на адекватность
                    {
                        if (matrix[i, j] == 1)
                        {
                            v[i] += 1;
                        }
                    }else
                    {
                        smezhnost = 1;
                    }
                }
                if (v[i] % 2 == 1) nechet++;
                if (v[i] == 0 || smezhnost==1 || matrix[i,i]!=0) { Console.WriteLine("Граф несвязный. Или ошибка в матрице."); break; }
                
            }
            if (smezhnost != 1)Console.WriteLine($"Нечетных вершин - {nechet}");
            if (nechet > 2 || nechet==1) Console.WriteLine("Нет ни цикла, ни цепи");
 
 
 
            int dlya_stacka = 0;
            if (nechet == 0) // пишем программу для нахождения цикла
            {
                //выберем стартовую вершину, например, будет 0.
                stack.Push(0); 
                while (stack.Count > 0)
                {
                        if (v[dlya_stacka] == 0) { otvet.Push(stack.Pop());} //когда пришли в вершину, где степень 0 - остается лишь вывести ответ
                        else
                        {//open
                                for (int j = 0; j < n; j++) //иначе будем проходить по смежным вершинам всегда
                                {
                                    if (matrix[dlya_stacka, j] == 1 && !(v[j]==1 && Smezh(matrix,dlya_stacka,n)>1)) //Smezh - ищет кол-во смежных вершин
                            { matrix[dlya_stacka, j] = 0; v[dlya_stacka] -= 1; v[j] -= 1; matrix[j, dlya_stacka] = 0; stack.Push(j); dlya_stacka = j;
                                        break;
                            }
                                }//выше мы вычитаем степени у вершин ребра, убираем в матрице смежности "смежности".
                                
                        }//close
                    
                }
 
                foreach (int number in otvet)
                {
                    Console.WriteLine(number+1); //вывод цикла.
                }
 
            }
            else
            {
                if(nechet==2) // пишем для поиска цепи.
                {
 
                }
            }
            Console.ReadKey();
        }
    }
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
25.03.2019, 20:57

Найти Гамильтонову цепь в непрерывном графе
Найти Гамильтонов цепи в непрерывном графе

Найти цикл в графе
Дан граф, содержащий только один цикл. Нужно найти его (все его вершины). Код не нужен, нужна...

Найти цикл в графе
matr (1,2) = 1; matr (2,6) = 4; matr (6,4) = 1; matr (4,1) = 2; matr (5,4) = 2; matr (7,5) =...

Эйлеров цикл
Есть программа: def euler_circuit(G): EP= # Эйлеров цикл - массив вершин. ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru