All Questions
Tagged with path-connected combinatorics
13 questions
3
votes
2
answers
106
views
Counting $10$ length paths in a $2 \times 4$ rectangle with distance $6$ units from start to end meaning negative moves allowed?
How many different routes of length 10 units (each side is 1 unit) are there to traverse from lower left corner (point A) to top right corner (point B) in a rectangle with 2 rows and 4 column cells ...
- 135
0
votes
0
answers
24
views
Count all possible paths on a grid while traversing to any surrounding tiles at least zero or one time(s) [duplicate]
This is a bit difficult to explain as I'm not a mathematician and don't know the correct terms, but I'll try my best. Any tips on improvement are welcome.
I did find this question but the requirements ...
- 1,002
4
votes
3
answers
293
views
How many ways for a beetle to move from bottom left corner to upper right corner in a 6 x 6 grid if it must be done in 14 steps only?
Note: We allow all four directions (up, down, right, left but no diagonal)
The 6 x 6 grid is composed of 7 horizontal lines and 7 vertical lines. We are to calculate how many 14 steps paths are ...
-1
votes
1
answer
111
views
Smallest $k$ to make sure the $k$-nearest-neighbor graph is connected
Given any $n$ points in $\mathbb{R}^d$, then make an undirected edge between every point and each of its $k$ nearest neighbors (in Euclidean distance). What is the smallest $k$ to make sure that the ...
- 2,066
0
votes
0
answers
36
views
Let points $A(x,y)$ and $B(x + 1,y)$ be points in an $(m + 1)*(n + 1)$ lattice starting at $O(0,0)$ and ending at $P(m,n)$.
So here is the Question :-
Let points $A(x,y)$ and $B(x + 1,y)$ be points in an $(m + 1)*(n + 1)$
lattice starting at $O(0,0)$ and ending at $P(m,n)$. Show that the number
of shortest paths from $O$ ...
- 324
1
vote
2
answers
2k
views
counting allowable/admissible paths on a grid with obstacles
I have a grid where some paths are removed.
where the following path is admissible,
but this path
is not.
How can I go about finding how many admissible paths are there on the following 2 grids (...
- 327
0
votes
0
answers
44
views
Making largest line in 10 × 10 grid.
How many blocks can you pass through at most in a 10 × 10 grid.
The Rules are
1. U cannot go over a line
2. You cannot lift the pencil.
3. You cannot allow the blocks you have passed through to make a ...
- 83
4
votes
1
answer
619
views
A question regarding a $k$-connected graph
I would like to show several things, some for general $k$-connected graphs and some for several instances ($k=2,3,...$).
First, I want to show that for every $k$-connected graph each subset $A\...
- 799
1
vote
1
answer
261
views
How to count number of vertices in a particular graph.
Let $4\leq r\leq \lfloor\frac{n}{2}\rfloor$ and $P_n$ be a path graph on $n\geq 2r$ vertices.
$V(P_n) = \{v_1,\ldots,v_n\}$.
We obtain a graph $H$ by adding a vertex $x$ to $P_n$ such that $x$ is ...
- 4,648
1
vote
0
answers
509
views
Proving vertex form of Menger's Theorem et al. without using capacity of vertices.
I'm teaching an undergrad course in graph theory and have just finished the proof of Max Flow/Min Cut. So far I have used Diestel's definition (more or less) of flow network as a digraph $G$ with a ...
- 514
2
votes
2
answers
738
views
Number of Paths from A to B
These type of questions that ask the Number of Paths are relatively easy when it a ordered grid,
However this one isn't:
How do I account for all the paths without counting. And when you are only ...
- 148
0
votes
0
answers
189
views
Notation or formula for matrix traversal?
This question: Password 'spatial' pattern? gave me ideas about the properties of "walks" (continuous or relative, ordered paths) of keyboards (matrices), and now I am curious if there is a way to ...
- 131
0
votes
1
answer
178
views
Number of independent partitions in a path of n nodes and number of partitions for a set of n-1 elements
I need to find a bijective proof that the number of independent partitions in a path of $n$ nodes and number of partitions of a set of $n-1$ elements are equal.
By independent partitions in a path we ...
- 103