CMI2011-B-01a

go_editor asked in Graph Theory May 19, 2016

681 views

1 vote

A multinational company is developing an industrial area with many buildings. They want to connect the buildings with a set of roads so that:

Each road connects exactly two buildings.
Any two buildings are connected via a sequence of roads.
Omitting any road leads to at least two buildings not being connected by any sequence of roads.

Is it always possible to colour each building with either red or blue so that every road connects a red and blue building?

cmi2011
descriptive
graph-coloring

go_editor asked in Graph Theory May 19, 2016

by go_editor

681 views

0 Comments

Please log in or register to add a comment.

Please log in or register to answer this question.

2 Answers

1 vote

we get a tree as the resulting data structure from the 3 rules given.the chromatic number of a tree is 2.

Falahamin answered May 14, 2020

by Falahamin

0 Comments

Please log in or register to add a comment.

0 votes

Go to this link for the answer

https://gateoverflow.in/47092/cmi2011-b-01b

Kushagra Chatterjee answered Apr 11, 2018

by Kushagra Chatterjee

0 Comments

Please log in or register to add a comment.

← Previous Next →

← Previous in category Next in category →

Related questions

1 vote

2 answers

go_editor asked in Graph Theory May 27, 2016

754 views

CMI2011-B-01b
A multinational company is developing an industrial area with many buildings. They want to connect the buildings with a set of roads so that: Each road connects exactly two buildings. Any two buildings are connected via a sequence of roads. ... preferred roads differing in at least one road? Substantiate your answers by either proving the assertion or providing a counterexample.

go_editor asked in Graph Theory May 27, 2016

by go_editor

754 views

cmi2011
descriptive
graph-theory
graph-connectivity

1 vote

1 answer

go_editor asked in Graph Theory May 27, 2016

557 views

CMI2011-B-02c
Let $G$ be a connected graph. For a vertex $x$ of $G$ we denote by $G−x$ the graph formed by removing $x$ and all edges incident on $x$ from $G$. $G$ is said to be good if there are at least two distinct vertices $x, y$ in $G$ such that both $G − x$ ... such that we cannot find three distinct vertices $u_1, u_2, u_3$ such that each of $G − u_1,\: G − u_2,$ and $G − u_3$ is connected.

go_editor asked in Graph Theory May 27, 2016

by go_editor

557 views

cmi2011
descriptive
graph-theory
graph-connectivity

1 vote

1 answer

go_editor asked in Graph Theory May 27, 2016

649 views

CMI2011-B-02b
Let $G$ be a connected graph. For a vertex $x$ of $G$ we denote by $G−x$ the graph formed by removing $x$ and all edges incident on $x$ from $G$. $G$ is said to be good if there are at least two distinct vertices $x, y$ in $G$ such that both $G − x$ and $G − y$ are connected. Given a good graph, devise a linear time algorithm to find two such vertices.

go_editor asked in Graph Theory May 27, 2016

by go_editor

649 views

descriptive
cmi2011
graph-theory
graph-connectivity

1 vote

1 answer

go_editor asked in Algorithms May 27, 2016

500 views

CMI2011-B-07b
A finite sequence of bits is represented as a list with values from the set $\{0,1\}$-for example, $[0,1,0], [1,0,1,1], \dots [ \: ]$ denotes the empty list, and $[b]$ is the list consisting of one bit $b$. For a nonempty list $l, \text{ head}(l)$ returns the first ... g2(n) if (n == 0) then return(0) else return f2(g2(n-1),g1(n)) endif What is the value of $g2(256)$ and $g2(257)$?

go_editor asked in Algorithms May 27, 2016

by go_editor

500 views

descriptive
cmi2011
algorithms
identify-function

Subscribe to GATE CSE 2024 Test Series

Subscribe to GO Classes for GATE CSE 2024

Quick search syntax

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true

Subjects

All categories
General Aptitude (3.5k)
Engineering Mathematics (10.4k)
- Discrete Mathematics (7.1k)
  - Mathematical Logic (2.5k)
  - Set Theory & Algebra (1.9k)
  - Combinatory (1.6k)
  - Graph Theory (1.1k)
- Probability (1.4k)
- Linear Algebra (1.1k)
- Calculus (792)
- Optimization (0)
Digital Logic (3.6k)
Programming and DS (6.2k)
Algorithms (4.8k)
Theory of Computation (6.9k)
Compiler Design (2.5k)
Operating System (5.2k)
Databases (4.8k)
CO and Architecture (4.0k)
Computer Networks (4.9k)
Artificial Intelligence (79)
Machine Learning (48)
Data Mining and Warehousing (25)
Non GATE (1.4k)
Others (2.7k)
Admissions (684)
Exam Queries (1.6k)
Tier 1 Placement Questions (17)
Job Queries (80)
Projects (11)
Unknown Category (870)

64.3k questions

77.9k answers

244k comments

80.0k users

Recent Blog Comments

category ?
Hi @Arjun sir, I have obtained a score of 591 in ...
download here
Can you please tell about IIT-H mtech CSE self...
Please add your admission queries here:...

Send feedback
Rank Predictor
College Prediction
Useful Links
FAQ
Corrections
Discuss
Copyright
Request
Testimonials
Chat Logs
Chat
Badges
Search tips
Exam Category
Blog Category
Blog Tags
Privacy
Test Series
GATER
Refund Policy
Terms and Conditions
Contact Us

Developed by Chun

CMI2011-B-01a

0 Comments

Please log in or register to add a comment.

Please log in or register to answer this question.

2 Answers

0 Comments

Please log in or register to add a comment.

0 Comments

Please log in or register to add a comment.

Related questions

Subscribe to GATE CSE 2024 Test Series

Subscribe to GO Classes for GATE CSE 2024

Recent Posts

Subjects

Recent Blog Comments