Toggle navigation
Mathematics
SAT
JEE
IMO
Vocabulary
Algorithms
Sign In
Subscribe to the weekly news from TrueShelf
Subscribe
Sort By:
trending ▼
date
0
Undergraduate
By
Shiva Kintali
on Aug. 12, 2012 | Updated Jan. 16, 2017
Finding perfect matching in bipartite graphs
Let \(G = (A,B)\) be a bipartite graph. Hall's theorem implies that \(G\) has a perfect matching if and only if \(|A| = |B|\) and for each \(X \subseteq A\), \(|X| \leq |\Gamma(X)|\), where …
Computer Science
Algorithms
matching
0
Undergraduate
By
Shiva Kintali
on June 26, 2012 | Updated Jan. 16, 2017
Complete balanced binary trees are graceful
Label the vertices of a tree (with \(n\) vertices) with integers from \(1\) to \(n\). Now label each edge with the absolute difference of the labels of its incident vertices. The labeling is said to b…
Mathematics
Graph Theory
graph labeling
0
Graduate
By
Shiva Kintali
on Aug. 8, 2012 | Updated Jan. 16, 2017
Halin's theorem and Mader's theorem
Prove the following : Halin's Theorem : (Easy) There is a node of degree \(k\) in any edge-minimal \(k\)-vertex-connected graph. Mader's Theorem : (Hard) In any edge-minimal \(k\)-vertex-connected …
Mathematics
Graph Theory
connectivity
0
Undergraduate
By
rajeshchitnis
on Aug. 2, 2012 | Updated Jan. 16, 2017
Numbers divisible by sum of their digits
Show that there is an infinite sequence of natural numbers \({p_1,p_2,\ldots}\) such that for every \(i\in \mathbb{N}\) the number \(p_i\) does not have 0 as any of its digits but is divisible by the …
Mathematics
Puzzles
Number Theory
Puzzles
divisibility
0
Undergraduate
By
Chandra Chekuri
on July 29, 2012 | Updated Jan. 16, 2017
Simple path containing three given nodes
Let \(G=(V,E)\) be an undirected graph. Describe a linear time algorithm that given \(G\) and three distinct nodes \(u,v,w\) decides whether there is a simple path in \(G\) that contains all of them.
Computer Science
Mathematics
Algorithms
Graph Theory
linear time algorithms
0
Graduate
By
Shiva Kintali
on June 6, 2012 | Updated Jan. 16, 2017
Algebraic dual of graphs
Let \(G\) be a connected graph. An algebraic dual of \(G\) is a graph \(G'\) such that \(G\) and \(G'\) have the same set of edges, any cycle of \(G\) is a cut of \(G'\), and any cut of \(G\) is a cyc…
Mathematics
Graph Theory
matroids
0
High School
By
Shiva Kintali
on June 21, 2012 | Updated Jan. 16, 2017
Togglers and Truthtellers
There are five people. Four of them are togglers, and the fifth person is a truthteller. A toggler tells either the truth or lie when you ask him a question. The second time you ask him a question…
Puzzles
Puzzles
logic puzzle
0
Undergraduate
By
TrueShelf Inc.
on Sept. 28, 2013 | Updated Jan. 16, 2017
Task assignment using Hall's Theorem
You are given a collection of tasks each of which must be assigned a time slot in the range {\(1,\dots,n\)}. Each task \(j\) has an associated interval \(I_j = [s_j,t_j]\) and the time slot assigned t…
Mathematics
Graph Theory
assignment
halls theorem
0
Undergraduate
By
Jagadish
on Nov. 3, 2012 | Updated Jan. 16, 2017
Array to Histogram
Given an array A[1..n] containing integers between 1 to n, transform the array to contain counts of each number in their respective positions. Your algorithm should run in linear time and constant ext…
Computer Science
Algorithms
linear time algorithms
0
Undergraduate
By
aa1062
on July 22, 2012 | Updated Jan. 16, 2017
Pecking order
A researcher is studying the social dynamics of chicken coops. In each coop, for each pair of chickens \(A\) and \(B\), there is a pecking relationship: either \(A\) pecks \(B\) or \(B\) pecks \(A\) (…
Mathematics
Graph Theory
tournament
« previous
1
2
3
...
23
24
25
26
next page »
icon
Sign In or Sign Up
icon
Invite Friends
Post Something
x
Select What You'd Like To Post
POST AN ARTICLE
POST AN EXERCISE
POST A MULTIPLE-CHOICE QUESTION
Content Types
Exercises
Multiple-Choice Questions
Levels
High school
Undergraduate
Graduate
Subjects
Mathematics
Computer Science
Puzzles
Optimization
Trending tags
geometry puzzle
pigeonhole principle
adjacency matrix
matrices
matrix multiplication
matching
sorting
math puzzle
imo
imo 2016
Topics
Algebra
Algorithms
Approximation Algorithms
Calculus
Combinatorial Optimization
Combinatorics
Complexity Theory
Data Structures
Discrete Mathematics
Game Theory
Geometry
Graph Theory
Linear Algebra
Linear Programming
Logic
Mathematics
Matrix Theory
Number Theory
Optimization
Probability
Programming
Puzzles
Randomized Algorithms
Real Analysis
Trigonometry
×