# Tagged Questions

39 views

### Check if there exists an undirected graph, given the degrees of its vertices [closed]

N-numbers , d1,d2,d3..dn are given. How do we check if it is possible to construct a undirected graph with vertices v1,v2,v3,...vn with degress d1,d2,...dn respectively. Graph should not contain ...
47 views

### Tricky algorithm for finding alternative route in graph with few added edges

Okay, so I found this a bit tricky. Basically, you have a directed graph (let's call it the base graph), that has some leaves and a node with 0 indegree that is called root. It may contain cycles. ...
100 views

### Find paths that cover all edges between two nodes

we hope you are able to help us with the following problem: A directed graph that may contain cycles is given. One has to find a set of paths that fulfill the following criterion: all edges that ...
127 views

### Running Time of Graph Algorithms

I am a bit confused on how to determine the running time of graph algorithms. That is, determining an estimated running time using the number of vertices (n) and the number of edges (m). Does ...
207 views

### the center of a tree with weighted edges

i am trying to give a solution to my university assignement..given a connected tree T=(V,E). every edge e has a specific positive cost c..d(v,w) is the distance between node v and w..I'm asked to give ...
424 views

### Algorithm to cover all edges given starting node

Working on an algorithm for a game I am developing with a friend and we got stuck. Currently, we have a cyclic undirected graph, and we are trying to find the quickest path from starting node S that ...
72 views

### Number of edges between the two subsets of a bipartitioned graph

Given a graph G=(V, E), a subset S that belongs to V, and the subset S' containing every vertex of G not belonging to S, I want to count the total number of edges between the nodes of S and S'. An ...
366 views

### Minimize set of edges in a directed graph keeping connected components

Here is the full question: Assume we have a directed graph G = (V,E), we want to find a graph G' = (V,E') that has the following properties: G' has same connected components as G G' has same ...
149 views

### Number of ways n-1 edges may be chosen to form a connected graph with n nodes

Basically, you require n-1 edges, to make a connected graph with n nodes. I would like to know if there is any theory behind finding the number of distinct ways you can select the n-1 edges, from the ...
180 views

### Least number of edges that appear in every path

I need to find the least number of edges in a graph that appear in every path from the first vertice to the last. For example - in the image if the first vertice is V0 and the last vertice is V8 then ...
440 views

### bellman ford algorithm trace

I don't know where else to post this question, I just want to know if I did this trace correct. I am given this diagram and here is the question: Show the trace of the Bellman-Ford algorithm on ...
474 views

### Draw a graph from a list of connected nodes

In a system I Have a list of nodes which are connected like in a normal graph. We know the whole system and all of their connections and we also have a startpoint. All my edges has a direction. Now I ...
562 views

### Build tree from edges

I have the edges and i want to build a tree with it. The problem is that i can construct my tree structure only when edges are in specific order. Example of orders: (vertex, parent_vertex) good: ...
322 views

### What is the best Implementation for a Multigraph?

In both space and operation cost which is the best way to implement a multigraph that has more edges than vertices? In the worst case it would have 5000 edges and 1000 vertices. I was thinking of ...
139 views

### Retrieving edges of a graph

I should create an algorithm to retrieve the list of edges (arcs) of a graph ADT. I can't access graph private members. I have thought I could do something similar to a DFS or BFS visit marking nodes ...
952 views

### Spring Graph Algorithm w Node size

I need to do some graph layout drawing and have been looking at using something like the Spring layout algorithm as implemented here and discussed here However my nodes all have a width and height ...
399 views

### How to find Edges and Vertices of a hand drawn polygon

I would like to make a shape recognition program that would trace a mouse and record it's location at each 1/2 second. how could I use these points to find a rough polygon? In other words, if you just ...
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}