Determine the maximum collection of edge-disjoint xy-paths in Q n </msub> Let x

Jonathan Miles 2022-07-01 Answered
Determine the maximum collection of edge-disjoint xy-paths in Q n
Let x be the vertex of all zeros and y be the vertex of all ones in the hypercube graph Q n . We have to determine the maximum collection of edge-disjoint xy-paths in Q n and a minimum vertex cut of Q n separating x and y.
My work: We define a xy-path P i as follows:
Start from the vertex x and change the i t h bit to 1 and then change all bits gradually one by one moving leftward from i 1 to 1 to n and back to i.
Note that all paths P i are edge-disjoint. Thus we have a maximum collection.
By Menger's Theorem, the second part follows.
You can still ask an expert for help

Want to know more about Discrete math?

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (1)

Alisa Jacobs
Answered 2022-07-02 Author has 13 answers
Step 1
The reasoning all the paths P i are edge-disjoint. Thus we have a maximum collection.
is nonsense. The empty set is a set of edge-disjoint paths. A set containing a single path is a set of edge-disjoint paths. There is nothing about being edge-disjoint that says your collection of paths is large in any way, let alone maximum.
You are not going to trick your way out of looking at cuts. If you think your collection of n edge-disjoint paths is maximum, find an edge cut of size n, and that will prove that you can't find a collection of n + 1 paths (by the easy direction of Menger's theorem).
Yes, I said edge cut. Edge-disjoint paths go with edge cuts. If you want something that goes with a vertex cut, you should be looking for a collection of internally (vertex-)disjoint paths: paths that don't share any vertices other than the endpoints.
Step 2
That being said: yes, none of your paths P 1 , P 2 , , P n share any edges or (which is stronger) vertices other than x or y. That's because all internal vertices of path P i have the following property: the i th bit is 1, and the the ( i + 1 ) th bit is 0. No other path P j with j i contains a vertex with this property, because every other path will set the ( i + 1 ) th bit to 1 before setting the i th bit to 1.
Did you like this example?
Subscribe for all access

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2021-08-15
How many elements are in the set { 0, { { 0 } }?
asked 2021-07-28

Let A, B, and C be sets. Show that (AB)C=(AC)(BC)
image

asked 2021-08-02

Suppose that A is the set of sophomores at your school and B is the set of students taking discrete mathematics at your school. Express each of these sets in terms of A and B. 
a) the set of sophomores taking discrete mathematics in your school 
b) the set of sophomores at your school who are not taking discrete mathematics 
c) the set of students at your school who either are sophomores or are taking discrete mathematics 
Use these symbols: 

asked 2021-08-18

Discrete Mathematics Basics

1) Find out if the relation R is transitive, symmetric, antisymmetric, or reflexive on the set of all web pages.where (a,b)R if and only if 
I)Web page a has been accessed by everyone who has also accessed Web page b.
II) Both Web page a and Web page b lack any shared links.
III) Web pages a and b both have at least one shared link.

asked 2022-07-17
Discrete Math Compositions
I am having trouble with these compositions.
T = { ( a , a ) , ( a , b ) , ( b , c ) , ( b , d ) , ( c , d ) , ( d , a ) , ( d , b ) }
U = { ( a , a ) , ( a , d ) , ( b , c ) , ( b , d ) , ( c , a ) , ( d , d ) }
I need to find T T, U T, and T U.
My problem is when I get down to, for example U T where (d,a) corresponds with both (a,a) and (a,c). This seems to happen for everyone of these problems. Is it even possible to take the composition of these?
asked 2022-06-24
Deriving variance of a branching process with generating functions
In lecture today my professor introduced the notion of branching processes, and left the derivation of Var ( X n + 1 ) to the students as an exercise. He said that we should try solving the problem through generating functions. For notation, let μ denote the average of the offspring distribution, and let σ 2 denote its variance. X n denotes the number of offspring present at time n, and it is assumed that X 0 = 1.
I began this by first deriving the recursive formula for Var ( X n + 1 ), which goes as follows:
Var ( X n + 1 ) = μ 2 Var ( X n ) + μ n σ 2
We can then define a generating function f(x) as follows:
Var ( X n + 1 ) = c n + 1 , f ( x ) = n = 0 c n x n = n = 0 c n + 1 x n + 1
So we have:
n = 0 c n + 1 x n + 1 = n = 0 ( μ 2 c n x n + 1 ) + n = 0 μ n σ 2 x n + 1
I eventually simplify this down to the form of:
f ( x ) = σ 2 x × 1 1 μ x × 1 1 μ 2 x
I'm new to generating functions, and don't have much experience with working with them. How do I pull out and isolate c n + 1 from the left-hand side of this expression? How would you guys finish this problem?
asked 2022-05-13
How to prove this inequality with the simplest means?
x 2 + 5 y 2 + 6 z 2 4 5 x y z 2 ,    if    x y > 0
I was trying to prove it. The right hand side should be nonnegative, so I can square it on both sides. But once I have done it I get to a point, where I do not see how to show, that the statement is greater or equal to 0.
x 4 + 25 y 4 + 36 z 4 + 10 x 2 y 2 + 12 x 2 z 2 + 60 y 2 z 2 80 x y z 2 0..

New questions

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question