Answer to Question #287879 in C++ for Ali

Question

Solve below problems with the help of graph terminology using Graph G. (15)

4.1. Does graph G has a Hamilton cycle if yes then redraw such cycle?

4.2. Is graph G a bipartite graph, if yes then redraw?

4.3. Does graph G have an Euler circuit? In case of yes redraw & in case of No, convert it

in an Euler form

4.4. Find a tree in the graph G and then redraw?

4.5. Convert graph G into map and fill with different colors. What is the chromatic

number?

4.6. Prove that graph G is a planner graph, if yes then redraw.

4.7. Write down the adjacency matrix for graph G.

` ★★★★★★

Answer 1

#include <iostream>
#include <queue>
#define V 4


using namespace std;


bool IsBipartite(int G[][V], int src)
{
    int fooBar[V];
    for (int i = 0; i < V; ++i)
        fooBar[i] = -1;


    fooBar[src] = 1;


    queue <int> q;
    q.push(src);


    while (!q.empty())
    {
        int u = q.front();
        q.pop();


        if (G[u][u] == 1)
        return false;


        for (int v = 0; v < V; ++v)
        {
            if (G[u][v] && fooBar[v] == -1)
            {
                fooBar[v] = 1 - fooBar[u];
                q.push(v);
            }


            else if (G[u][v] && fooBar[v] == fooBar[u])
                return false;
        }
    }


    return true;
}


int main()
{
    int G[][V] = {{1, 1, 0, 1},
                {1, 0, 1, 0},
                {0, 1, 1, 1},
                {1, 0, 1, 0}
            };


    IsBipartite(G, 0) ? cout << "Yes" : cout << "No";
    return 0;
}