Given a graph with $ n$ nodes . The adjacency matrix of the graph is given. We do $ k$ operations on this graph. In each operation we choose two distinct nodes $ i$ and $ j$ (there are $ (n*(n-1))/2$ such choices) equiprobably (all choices are equiprobable) and if there exists a edge between $ i$ and $ j$ we delete that edge or else we draw an edge between the chosen pair of nodes.

We have to output a $ n*n$ matrix where the element at $ (i,j)th$ position denotes the probability of occurrence of edge connecting the nodes $ i$ and $ j$ in the final resulting graph.

The constraints on n and k are $ n<=50$ and $ k<=50$ .

I tried it using dynamic programming but could figure out transitions properly.

Can you please help me out.

# Tag: Nodes

## No of ways of selecting k non adjacent nodes in a graph for all k

Suppose there is an undirected connected graph with n<=38 nodes without multiple edges and self loops . We have to find the no. Of ways to select k nodes such that no two of them are adjacent for all possible k efficiently

## Directed Grid Graphs; All Possible Paths Through Nodes

I have a problem in which I am interested in taking a matrix of positive integer weights, including zero, where the matrix has dimensions nrow x ncol and the columns always sum to the same arbitrary number. I want to search for a list of paths (sets of edges essentially) that traverse through the grid space of the same dimension & create the paths such that the # of edges in a path going through a node is equal to the nodes weight (from the matrix). Ie: if a particular index in my matrix was "3", there would be 3 edges that would run into (and out of) this node.

Some important restrictions. Firstly, The only direction the edges can move is rightward (so vertical edges are disallowed) but only one column distance at a time. I do allow for the edges to go from any row_j (in column_i) to any other possible row_j in column_i+1, so diagonal edges (either upwards or downwards are allowed). Here’s an example of such a solution (it is non singular which is why Im interested in ALL possible paths)

Most importantly, I am interested in two things. First I want all possible paths from this process, and even more critically, I want to minimise the number of possible diagonal edges that my resulting paths will contain.

Any sort of algorithm here to solve this would be hugely helpful.

I have managed to solve the case when I don’t care about the number of diagonal edges, and just want a set of paths that match with the weights. To do that, I used the weights at adjacent columns to generate a Markov transition process. This gave me a series of transition matrices (of length ncol-1) which from there I was able to construct probabilistically what my paths through my weights were.

Let me know if anyone needs any more details/explanations here.

## Should copied doubly-linked graph nodes create links from preexisting nodes?

Say I have a graph with doubly linked nodes. Node C has links *from* nodes A and B, which both have links *to* C, and node C has links *to* nodes D and E, which both have links *from* node C.

I now copy node C to create node C2. Should nodes A, B, D, and E all now have links to C2?

## What is the upper bound on the number of nodes in a tree with n leaves where each internal node has at least two children?

The pieces of information available to us are the number of leaves in a tree and that each internal node must have at least two children. Is there a way to find the upper bound on the total number of nodes in the tree?

## Product of all nodes except for one in Binary Tree

Assume we are given a binary tree with an integer sitting at each node. I am looking for an efficient way to find for every path from the root to a leaf every possible product with exactly one node omitted. I am looking for a solution without divisions (i.e. integers can be zero).

One way to go about this I thought of is I can compute all possible partial products starting at the root. That is each node stores the product of the unique path from the root up this node ( but except the integer stored at that particular value ). Then for each leaf node I can walk up the path to the root node multiplying the integers on the way. At a given node before accumulating the node into the product I can multiply the product with the prefix product stored in the node.

It feels like I am doing a lot of redundant multiplications when visiting each path from a leaf to the root, since these paths potentially share a lot of nodes. Is there a way faster way to do this?

## Covering nodes in a tree

Following scenario:

I have a neighbourhood represented as a tree where each node is a house and I want to cover the whole neighbourhood with a signal.

An antenna of strength **0** can only provide a signal to **itself**. An antenna of strength **j** can provide a signal to itself and nodes that are **j steps away** from it. The cost of building an antenna at a house is given by a cost function while the cost of building a an antenna of strength **i** has to be **less than or equal** to building an antenna of strenth **j**, if **i is weaker than j**.

` g | f / | \ c d e / \ a b `

For example an optimal solution in this tree for a cost function

`f(i) = i + 1 `

where i is the strength of the antenna, would be to place an antenna of strength 2 at node f.

This is a school assignment and the ultimate goal is to write a dynamic programm that can solve it in O(n^2). As far as my understanding goes the ‘trick’ of dynamic programming is to find a recursive algorithm that can solve the problem in exp. time and then use a table to cache the intermediate answers that build upon each other to improve the time complexity.

My problem is that I fail to see a recursion in the problem and can’t seem to make any progress why I would appreciate if someone could point me in the right direction.

## How to find all paths of length up to k between two nodes in a directed graph?

Let’s say I have a directed graph represented as an adjacency matrix, and I’m given two nodes $ u,v$ and a parameter $ k$ . Let’s also say that the maximal degree of a node in the graph is $ d$ .

What is the most efficient algorithm to find all paths of length $ <=k$ from $ u$ to $ v$ ?

I know the number of such paths can be calculated efficiently using Dynamic Programming approach, but I’m looking for an algorithm that allows to get a set of actual paths.

It’s clear that such algorithm would have a factor of the number of paths in its time complexity, which has $ k$ in the exponent, but still, I would like to know what is the best approach for such a problem.

## Algorithm design: find any path in an undirected acyclic graph which has a total sum of the nodes as a specific value

The question was asked in an interview, and I’m not sure if this is the most optimized answer, but here goes-

You have an undirected acyclic graph, where each node has a non-negative value `x`

and the edges have 0 value. You need to find a path with any number of nodes on it such that the total sum of all node values is exactly `k`

. There are `N`

nodes in the graph. You can start at any node.

I gave the brute-force solution for this problem, which is basically do a dis on each node until you find a valid “root” node, such that it has a path to one of the other nodes, with a total sum being `k`

. The time complexity of this solution would be `n^2`

, since we are doing DFS on each node.

The question was posed as a delivery problem, where you have `N`

connected houses, each having a package of weight `k`

, and the truck can start at any house and should follow a path, and has to pick the package from every house that is on that path. The weights should sum exactly to `k`

.

## Number of nodes in a B-Tree given approximate degree and number of items to store

In Fredman and Willards paper “Surpassing the Information Theoretic Bound with Fusion Trees” They mention that the number of nodes in a B-Tree is $ O(N/B^4)$ , where $ N$ is the number of keys they store in the tree, and $ B$ is the approximate degree.

I am not quite sure how they got this result, reading the original paper on B-Trees, Bayer and McCreight only mention a bound for a tree with height $ h$ , and approximate degree $ B$ , however not one for the number of keys to store. They give the following bound where $ N(T)$ is the number of nodes in a tree $ T\in\tau(B,h)$ . (approximate degree $ B$ and height $ h$ ) $ $ 1+\frac{2}{B}((B+1)^{h-1}-1)\leq N(T)\leq \frac{1}{2B}((2B+1)^h-1)$ $ Is there any way i could go from this, to Fredman and Willards $ O(N/B^4)$ ?