Learning starts with a question
First time here? Checkout the FAQs!
x

*Math Image Search only works best with zoomed in and well cropped math screenshots. Check DEMO

0 like 0 dislike
35 views
Prove that for each DAG there is a topological ordering
in Data Science & Statistics by Platinum (141,884 points) | 35 views

1 Answer

0 like 0 dislike
Best answer

Proof.

By induction, we need to show that in each DAG, there is a node without any ancestors.

Start with any node and move to one of its parents (if there are any).

You will never visit a parent that you have seen before (if you did there had been a directed cycle).

After at most \(p-1\) steps you reach a node without any parent.

by Platinum (141,884 points)

Related questions

0 like 0 dislike
0 answers
0 like 0 dislike
1 answer
asked Nov 22 in Data Science & Statistics by MathsGee Platinum (141,884 points) | 29 views
0 like 0 dislike
1 answer
1 like 0 dislike
1 answer
1 like 0 dislike
0 answers
asked May 11, 2021 in Mathematics by Sabelo Letsoalo Wooden Status (150 points) | 124 views
0 like 0 dislike
0 answers
asked May 11, 2021 in Mathematics by Sabelo Letsoalo Wooden Status (150 points) | 116 views
0 like 0 dislike
1 answer
asked Apr 26, 2020 in Mathematics by MathsGee Platinum (141,884 points) | 164 views
1 like 0 dislike
1 answer
asked Aug 14, 2021 in Mathematics by MathsGee Platinum (141,884 points) | 184 views
0 like 0 dislike
1 answer
0 like 0 dislike
1 answer
asked May 10, 2021 in Mathematics by MathsGee Platinum (141,884 points) | 217 views
0 like 0 dislike
0 answers

Join the MathsGee Q&A forum where you get STEM education support to succeed from our community. Connect and Learn.


On the MathsGee Q&A Forum, you can:


1. Ask questions


2. Answer questions


3. Vote on questions and answers


4. Start a fundraiser


5. Tip your favorite community members


6. Create Live Video Tutorials (Paid/Free)


7. Join Live Video Tutorials (Paid/Free)


8. Earn points by participating



MathsGee Q&A forum post


1. Remember the human


2. Act like you would in real life


3. Find original source of content


4. Check for duplicates before publishing


5. Read the community guidelines




FORUM RULES


1. Answers to questions will be posted immediately after moderation


2. Questions will be queued for posting immediately after moderation


3. Depending on the number of messages we receive, you could wait up to 24 hours for your message to appear. But be patient as posts will appear after passing our moderation.




USEFUL LINKS


Acalytica | Web Analytics | SEO Reports | Social Proof Tool | Email Marketing


MathsGee Android Q&A