Maximum number of path for simple acyclic directed graph with start and end node

Thread starter jack1234
Start date Jan 22, 2013
Tags

Graph Maximum Path

AI Thread Summary

In a simple acyclic directed graph with n nodes, the maximum number of paths from a starting node s0 to an ending node e0 can be determined using the powers of the nilpotent adjacency matrix. The adjacency matrix captures the connections between nodes, and its powers can reveal the number of distinct paths of varying lengths. Specifically, the entries in the matrix indicate the number of paths of a certain length between nodes. The maximum number of paths is influenced by the structure of the graph and the arrangement of nodes. Understanding this relationship is crucial for analyzing path counts in directed acyclic graphs.

Jan 22, 2013

jack1234

Say given a simple acyclic directed graph with n nodes , which includes a starting node s0 and ending node e0 (i.e., a kripke structure without loop)
what is the maximum number of path from s0 to e0?

Physics news on Phys.org

Jan 23, 2013

bpet

The solution could be written in terms of powers of the (nilpotent) adjacency matrix.

Thread 'Deductive proof in logic formal systems'

I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...

View full post »

Thread 'Onto set mapping is the surjective set mapping, and into injective?'

The textbook is being fine. I asked the forum for some introduction to topology, and decided to start with Simmon`s. This naive question is due to ignorance of the words into and onto, which I don't distinguish in Spanish. A quick browsing sugests I'm right.

View full post »