Рубрики

Максимальное количество ребер в двудольном графе

Дано целое число N, которое представляет количество вершин. Задача состоит в том, чтобы найти максимально возможное число ребер в двудольном графе из N вершин.

Двудольный график:

  1. Двудольный граф — это граф с двумя наборами вершин.
  2. Множество таково, что вершины в одном наборе никогда не будут делить ребро между ними.

Примеры:

Input: N = 10
Output: 25
Both the sets will contain 5 vertices and every vertex of first set
will have an edge to every other vertex of the second set
i.e. total edges = 5 * 5 = 25

Input: N = 9
Output: 20

Подход: число ребер будет максимальным, когда каждая вершина данного набора имеет ребро для каждой другой вершины другого набора, то есть, ребра = m * n, где m и n — количество ребер в обоих наборах. чтобы максимизировать количество ребер, m должно быть равно или максимально близко к n . Следовательно, максимальное количество ребер можно рассчитать по формуле:

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

C ++

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

using namespace std;

  
// Функция для возврата максимального числа
// ребер возможно в двудольном
// граф с N вершинами

int maxEdges(int N)

{

    int edges = 0;

  

    edges = floor((N * N) / 4);

  

    return edges;

}

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

int main()

{

    int N = 5;

    cout << maxEdges(N);

  

    return 0;

}

Джава

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

  

class GFG {

  

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

    // ребер возможно в двудольном

    // граф с N вершинами

    public static double maxEdges(double N)

    {

        double edges = 0;

  

        edges = Math.floor((N * N) / 4);

  

        return edges;

    }

  

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

    public static void main(String[] args)

    {

        double N = 5;

        System.out.println(maxEdges(N));

    }

}

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

python3

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

  
# Функция для возврата максимального числа
Число ребер возможно в двудольном
# граф с N вершинами

def maxEdges(N) : 

  

    edges = 0

  

    edges = (N * N) // 4

  

    return edges; 

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

if __name__ == "__main__" :

      

    N = 5

    print(maxEdges(N)); 

  
# Этот код предоставлен AnkitRai01

C #

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

using System;

  

class GFG {

  

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

    // ребер возможно в двудольном

    // граф с N вершинами

    static double maxEdges(double N)

    {

        double edges = 0;

  

        edges = Math.Floor((N * N) / 4);

  

        return edges;

    }

  

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

    static public void Main()

    {

        double N = 5;

        Console.WriteLine(maxEdges(N));

    }

}

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

PHP

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

  
// Функция для возврата максимального числа
// ребер возможно в двудольном
// граф с N вершинами

  

function maxEdges($N)

{

    $edges = 0;

  

    $edges = floor(($N * $N) / 4);

  

    return $edges;

}

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

    $N = 5;

    echo maxEdges($N);

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

Выход:

6

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

Максимальное количество ребер в двудольном графе

0.00 (0%) 0 votes