Программа на Java для поиска хроматического индекса циклических графов
Хроматический индекс графа - это минимальное количество цветов, необходимых для окраски ребер графа, чтобы любые два ребра, которые имеют одну и ту же вершину, имели разные цвета.
Принимая во внимание, что циклический граф - это граф, который содержит по крайней мере один цикл графа, то есть циклический означает путь по крайней мере от одного узла обратно к самому себе. Здесь дан циклический граф, мы должны найти хроматический индекс этого графа.
Примеры:
Input: e = 12
edges = {{ 1, 2}, { 2, 3}, { 3, 4},
{ 4, 1}, { 5, 6}, { 6, 7},
{ 7, 8}, { 8, 5}, { 1, 8},
{ 2, 5}, { 3, 6}, { 4, 7}}
Output: Chromatic Index = 3
Explanation:
Подход:
Применяя теорему Визинга, мы можем доказать, что данный граф может иметь хроматический индекс «d» или «d» + 1, где d - максимальная степень графа.
Ниже приведен пошаговый подход к алгоритму: -
- Инициализируйте количество ребер и список ребер.
- Раскрасьте график в соответствии с теоремой Визинга.
- Назначьте цвет кромке и проверьте, имеют ли смежные кромки одинаковый цвет или нет.
- Если любой соседний край имеет тот же цвет, увеличьте цвет, чтобы попробовать следующий цвет для этого края.
- Повторяйте, пока все края не приобретут свой цвет согласно теореме.
- После этого напечатайте максимальное значение цвета для всех краев и цвета каждого края.
Ниже представлена реализация описанного выше подхода:
Ява
// Java program to find the chromatic// index of a cyclic graphimport java.util.*; public class chromaticIndex { // Function to find the chromatic index public void edgeColoring( int [][] edges, int e) { // Initialize edge to first // edge and color to color 1 int i = 0 , color = 1 ; // Repeat until all edges are done coloring while (i < e) { // Give the selected edge a color edges[i][ 2 ] = color; boolean flag = false ; // Iterate through all others edges to check for ( int j = 0 ; j < e; j++) { // Ignore if same edge if (j == i) continue ; // Check if one vertex is similar if ((edges[i][ 0 ] == edges[j][ 0 ]) || (edges[i][ 1 ] == edges[j][ 0 ]) || (edges[i][ 0 ] == edges[j][ 1 ]) || (edges[i][ 1 ] == edges[j][ 1 ])) { // Check if color is similar if (edges[i][ 2 ] == edges[j][ 2 ]) { // Increment the color by 1 color++; flag = true ; break ; } } } // If same color faced then repeat again if (flag == true ) { continue ; } // Or else proceed to a new vertex with color 1 color = 1 ; i++; } // Check the maximum color from all the edge colors int maxColor = - 1 ; for (i = 0 ; i < e; i++) { maxColor = Math.max(maxColor, edges[i][ 2 ]); } // Print the chromatic index System.out.println( "Chromatic Index = " + maxColor); } // Driver code public static void main(String[] args) { // Number of edges int e = 4 ; // Edge list int [][] edges = new int [e][ 3 ]; // Initialize all edge colors to 0 for ( int i = 0 ; i < e; i++) { edges[i][ 2 ] = - 1 ; } // Edges edges[ 0 ][ 0 ] = 1 ; edges[ 0 ][ 1 ] = 2 ; edges[ 1 ][ 0 ] = 2 ; edges[ 1 ][ 1 ] = 3 ; edges[ 2 ][ 0 ] = 3 ; edges[ 2 ][ 1 ] = 4 ; edges[ 3 ][ 0 ] = 4 ; edges[ 3 ][ 1 ] = 1 ; // Run the function chromaticIndex c = new chromaticIndex(); c.edgeColoring(edges, e); }} |
Хроматический индекс = 2
Выход:
Хроматический индекс = 2
Рекомендации:
- визингс-теорема
- https://en.wikipedia.org/wiki/Vizing%27s_theorem
Вниманию читателя! Не прекращайте учиться сейчас. Ознакомьтесь со всеми важными концепциями Java Foundation и коллекций с помощью курса "Основы Java и Java Collections" по доступной для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .