Рубрики

Программа для поиска номера региона в Планарном Графе

Даны два целых числа V и E, которые представляют количество вершин и ребер плоского графа . Задача состоит в том, чтобы найти количество областей этого плоского графа.

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

Область: Когда плоский граф рисуется без пересечения ребер, ребра и вершины графа делят плоскость на области.

Примеры:

Input: V = 4, E = 5
Output: R = 3

Input: V = 3, E = 3
Output: R = 2

Подход: Эйлер выяснил количество областей в плоском графе как функцию от числа вершин и числа ребер в графе, т.е.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Функция для возврата числа
// областей в плоском графе

int Regions(int Vertices, int Edges)

{

    int R = Edges + 2 - Vertices;

  

    return R;

}

  
// Код драйвера

int main()

{

    int V = 5, E = 7;

  

    cout << Regions(V, E);

  

    return 0;

}

Джава

// Java реализация подхода

import java.io.*;

  

class GFG {

  

    // Функция для возврата числа

    // областей в плоском графе

    static int Regions(int Vertices, int Edges)

    {

        int R = Edges + 2 - Vertices;

  

        return R;

    }

  

    // Код драйвера

    public static void main(String[] args)

    {

  

        int V = 5, E = 7;

        System.out.println(Regions(V, E));

    }

}

  
// Этот код предоставлен akt_mit

python3

# Python3 реализация подхода

  
# Функция для возврата номера
# регионов в плоском графике

def Regions(Vertices, Edges) : 

  

    R = Edges + 2 - Vertices; 

  

    return R; 

  
# Код драйвера

if __name__ == "__main__"

  

    V = 5; E = 7

  

    print(Regions(V, E)); 

  
# Этот код добавлен
# by AnkitRai01

C #

// C # реализация подхода

using System;

  

class GFG {

  

    // Функция для возврата числа

    // областей в плоском графе

    static int Regions(int Vertices, int Edges)

    {

        int R = Edges + 2 - Vertices;

  

        return R;

    }

  

    // Код драйвера

    static public void Main()

    {

  

        int V = 5, E = 7;

        Console.WriteLine(Regions(V, E));

    }

}

  
// Этот код предоставлен ajit

PHP

<?php
// PHP реализация подхода

  
// Функция для возврата числа
// областей в плоском графе

function Regions($Vertices, $Edges)

{

    $R = $Edges + 2 - $Vertices;

  

    return $R;

}

  
// Код драйвера

$V = 5; $E = 7;

echo(Regions($V, $E));

  
// Этот код добавлен
// по Code_Mech
?>

Выход:

4

Рекомендуемые посты:

Программа для поиска номера региона в Планарном Графе

0.00 (0%) 0 votes