Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with graph-theory
Search options not deleted
user 29697
Questions about the branch of combinatorics called graph theory (not to be used for questions concerning the graph of a function). This tag can be further specialized via using it in combination with more specialized tags such as extremal-graph-theory, spectral-graph-theory, algebraic-graph-theory, topological-graph-theory, random-graphs, graph-colorings and several others.
2
votes
Accepted
Are all subdivisions of bipartite graphs also bipartite?
I can write up this one. It looks like the definition of subdivision of a graph $G = (V,E)$ is: for every edge $\{u,v\}$, create a new vertex $w_{u,v}$. Make a new edge $\{u,w_{u,v}\}$ and a new edge …
- 4,529
6
votes
Algorithm to find the “optimal” path in a given graph
I think we can transform your problem into a standard shortest-path problem. The key points are
The magnitudes of the heights don't matter, just the order (because we want to find the path from $u$ …
- 4,529
1
vote
Accepted
Almost all simple graphs are small world networks
whether there is an elementary proof that almost all simple graphs are very small world networks
Following up on Brendan McKay's comment. The chance that an Edos-Renyi$(0.5,n)$ graph has diameter …
- 4,529
3
votes
Accepted
What do shortest-path algorithms actually calculate?
Computer Science often (usually, in my experience) defines a path as a sequence of vertices with edges between them, i.e. what others call a walk. E.g. on my shelf, this definition appears in Algorith …
- 4,529
11
votes
Accepted
Probability of a graph procedure
Here's one. You can think of the graph construction process as gradually building a set $S$ of vertices that have been touched so far, beginning with a random two vertices. Let $S_k$ be the set of the …
- 4,529
1
vote
Vertex degree on random graphs
Just an amateur answer, I would assume there's a paper or known approach out there from experts.
I would partition the vertices into equal sets $U,V$ and delete edges to make it a bipartite graph. It …
- 4,529
-1
votes
Maximum matching in a graph with no "shortcuts"
I think we can use a greedy-type algorithm based on topological sorting into layers. Due to Tony's answer, we know we can ignore the no-shortcuts assumption, so take any DAG with in-degree and out-deg …
- 4,529
2
votes
Accepted
Significance of the Eigenvalues of the adjacency matrix of a weighted di-graph
Your idea is pretty much spot on; this is the area of spectral graph theory. Often the graph Laplacian is used rather than its adjacency matrix -- the Laplacian is defined as $L = D - A$ where $A$ is …
- 4,529