Answering questions about graph theory

Thanks homie, downloaded Bondy and Murty 5e on your suggestion. It's from 1985; is that too old for a graphs text?
I had considered this as an afterthought in my discrete math class where I was introduced to graphs, but would you say there's an injection from any undirected graph G to a unique directed graph H such that for every link (Gv1 Gv2) in G there are two links (Hv1 -> Hv2) and (Hv2 -> Hv1)?
As in, undirected graphs are a special case of directed graphs, where all links have a converse?

Should add to that last question that every link has the same cost/weight/whatever-associated-property-or-value as its converse.

Here's a 2008 edition of Bondy & Murty, it's a bit more polished than the 1985 edition: classes.cs.uchicago.edu/archive/2016/spring/27500-1/hw3.pdf

Yes, you can certainly think of undirected graphs as directed graphs with each edge going both ways. You do get a unique directed graph corresponding to your undirected graph that way.

You can also do the reverse, i.e., given a directed graph D, you can construct an undirected graph G where you replace directed edges in D by undirected edges in G. G is called the underlying undirected graph of D

What are some way to characterize and count the number of spanning trees in an n-valent cyclic graphs? This can be used to find bounds on Feynman diagrams.

Counting the number of spanning trees of any graph can be done efficiently; listing all the different spanning trees in general cannot be done efficiently.

For the counting problem, see Kirchhoff's theorem. Basically, to get the number of spanning trees of a graph, multiply the graph's nonzero Laplacian eigenvalues and divide by n.

For the listing problem, you can use a deletion-contraction recursive algorithm on the edges of the graph; however, since there could be exponentially-many different spanning trees, you can only expect this algorithm to handle graphs up to around 60-70 vertices.

Unfortunately just counting/Kirchhoff's theorem wouldn't be enough for bounding Feynman diagrams even for the case with local delta interactions, since you have free and interacting propagators that you need to consider separately in the graph.
So finding spanning trees is in general NP? I wonder if quantum computing can change that.

Well, just generating distinct spanning trees one-after-another is easy; the thing is, there could be an exponential number of them for a given graph, so if you want to generate ALL of them, you would necessarily need an exponential number of steps. In fact, you would need an exponential amount of memory to store all these trees.

But if just generating a few spanning trees is enough for your application, then that's easy.

If you want to generate spanning trees with some special properties, then that could be easy or hard depending on the properties.

For example, if you want to generate the spanning trees which have the largest possible number of leaves, that's hard.
If you assign some weights to the edges and you want to generate the spanning trees which have the largest possible total edge weights, that's easy.

what's all this nerd shit ITT? this is even worse than those lines with y and x axes, get a life fucking losers LOL

What should I practice more between maximum flow, coupling and minimal spanning tree?

The special properties are determined by the number of edges ending upon a vertex, so I think I do have to do case enumeration.

found the PDE guy

are you practicing for a test or what?
min spanning tree is easy, just keep picking the smallest edge that doesn't create a cycle.
max flow is a bit harder, you should probably practice that. What's coupling? Do you mean matching?

is it the number of edges incident to one specific fixed vertex in the graph, or the min/max branchpoint degree of the tree, or something else? For the first of those, you may be able to modify deletion-contraction to give you only the spanning trees you need, rather than enumerating all of the spanning trees, and then finding the ones that have your desired property

Why is there a bijection between the distance-regular graphs on n vertices and the divisions by chords of a circle into n equal areas?

To clarify, if you divide a circle into equal pieces using only chords, and then make a graph such that each piece is a vertex and the vertices which represent adjacent pieces are joined by an edge.

If I understand the problem correctly, I don't think there is a bijection.

A distance regular graph has to be regular, i.e., all vertex degrees are the same.
You can certainly draw two chords like pic related which divide a circle into 3 equal areas.
Then, the graph obtained by connecting adjacent pieces is not regular (and hence not distance regular).

Does that make sense? Did I misunderstand the question?

Objection meaning the number of distance-regular graphs on n vertices is the sane as the number of chord divisions of the circle. I don't mean that the chord division graphs are distance regular.

*bijection

Oh I see.
So you want a bijection between the set of graphs resulting from chord divisions of a circle into n areas, and the set of distance-regular graphs on n vertices?

Can chords cross or no?

Yes chords can cross. What I've found about such graphs is they are outerplanar, bipartite, and no vertex connects more than two blocks. But that does not completely describe them.

reduce vertex cover to set cover right now

hmm. interesting. I'm not sure off the top of my head, but I'll think about it.
Does this problem come from HW or research? I assume the former, since you already know that there is a bijection. If so, what kind of chapter was it in? Probably the surrounding material will give some hint to the proof techniques

Given an instance (G,k) of Vertex Cover, we will construct an instance of Set Cover.
Suppose the vertices of G are labeled 1,...,n. Let U = E and let S_i be the set of edges incident to vertex i.

We can then show that (G,k) is a yes instance of Vertex Cover if and only if (U,S_1,...,S_n,k) is a yes instance of Set Cover.

Original research. I should admit that I don't actually know for sure there is a bijection, just that I've tested it for a lot of n and it seems too much to be a coincidence.

Ah alright, I'll think about it and let you know if I come up with anything.
It sounds pretty non-trivial though.
Results about distance-regular graphs are few and far in between.

is there exists way to find Hamiltonian cycle in graph for polynomial time?

In general, no.
If you assume your graph has some special structure, then yes.

Also, there is pretty good software for this problem:
math.uwaterloo.ca/tsp/concorde.html
(You can transform Hamilton Cycle to TSP by giving all edges in the complement of G infinite weights)

Best intro books on graph grammars?
Any interesting books or papers relating graph theory to logic?

>>graph grammars
wew lad. what do you want to do with graph grammars? Need any software for doing graph grammars?

Rozenberg is the go-to intro book
"Graph and Model Transformation" by Ehrig et al looks interesting too, I don't have that one but Ehrig is a pro in that field (or was, since he died last year). You can read some of his papers from the last decade for more connections between logic and graphs.

Other people you want to look up are
Goldberg, Nesetril, Tanatau, Elberfeld, and Jakoby. I've read a bunch of their work and it's all good

That question asks if P=NP and we all very well know there's currently no proof for that or even proof that it's provable.

D. Bonchev, "Chemical Graph Theory: Introduction and Fundamentals"
English | 1991 | ISBN: 0856264547 | PDF | pages: 235 | 33,4 mb

This volume presents the fundamentals of graph theory and then goes on to discuss specific chemical applications. Chapter 1 provides a historical setting for the current upsurge of interest in chemical graph theory. chapter 2 gives a full background of the basic ideas and mathematical formalism of graph theory and includes such chemically relevant notions as connectedness, graph matrix representations, metric properties, symmetry and operations on graphs. This is followed by a discussion on chemical nomenclature and the trends in its rationalization by using graph theory, which has important implications for the storage and retrieval of chemical information. This volume also contains a detailed discussion of the relevance of graph-theoretical polynomials; it describes methodologies for the enumeration of isomers, incorporating the classical Polya method, as well as more recent approaches.

basically anything written by a German author or with this bird on it is good.

do you do anything with graph grammars?

How do I create an admissable heuristic for a graph with random vertices and random weight edges? The problem is the vertices don't have coordinates.

Are zeta functions in graph theory a meme?

I like formal languages, computability, and graph theory. I've been interested in graph grammars for a while but haven't invested time into searching for intro resources.

Also, a few years ago I stumbled on a pair of really interesting PhD dissertations on 'Knowledge Graphs' from the University of Twente. I know the concepts aren't really related but in general I'd like to flesh out my knowledge base on other graph theory areas of research.

Thanks user, I'll check out those resources!

Care to give more info on that bird?

What are some generally considered efficient algorithms for finding the genus of an undirected graph?

Are there uncountable graphs and if so, can they be used to define a dimension independent integral measure?

>are you practicing for a test or what?
Having a test next week, but I have barely worked this semester. I have a lot of free time this week though, so I figured out I was going to do graphs like a turbo autist. Besides, I want to remain #1 in my class and I've worked on nearly all my group projects this semester with lazy faggots, so I have a lot of work to catch up for that.

>What's coupling? Do you mean matching?
Yes. I was shown the basic algorithm with alternating paths, but I missed the rest because lack of sleep.

a heuristic to do what?
Probably, I'm not aware of any useful applications of zeta functions in graph theory
generally for this problem, heuristics are preferred to exact algorithms; I'm not aware of any great exact algorithms. Due to the applications of graph embedding, people usually study the problem from a complexity point of view (rather than numerically, e.g. by integer programming) and the available algorithms are practically un-implemntable or have large hidden constants.
One exception to this is the following paper:
tcs.informatik.uos.de/_media/pubs/sea16_preprint_mingenus.pdf
They have some apparently decent IP models; you could email the authors to see if they'll give you their code.

See also Book embeddings of graphs, and the related algorithms for that, as they are often interconnected

I suppose you could define a graph with an uncountably infinite set of vertices, but it's not an object that has received much interest. You might as well not even call it a graph, since much of graph theory is going to be useless when working with this "uncountable graph" object

>I suppose you could define a graph with an uncountably infinite set of vertices, but it's not an object that has received much interest. You might as well not even call it a graph, since much of graph theory is going to be useless when working with this "uncountable graph" object
au contraire, piggot

en.wikipedia.org/wiki/Hadwiger–Nelson_problem
en.wikipedia.org/wiki/De_Bruijn–Erdős_theorem_(graph_theory)

What is a piggot? Is it perhaps a portmanteau of "pig" and "faggot", meaning "pig-faggot"?

Enough of your piggot oinkery

Why aren't there many more graph database implementations like there are numerous relational sql databases (for example mssql, oracle, mysql, postresql)? I know there is already one but written in Java, would having one more graph database implementation written in not Java something like C or C++ be useful?

>piggot
stop saying that. just shut your fucking mouth right now. that's not a meme. just stop. I swear to god if you retards say piggot one more time

You seem a little flustered... piggot.

What are the most important areas of graph theory to know for algorithms / computer science?

Also, can you give me an ELI5 or what Ramsey theory is and why it's important?

Is there any tool for solving both floorplanning with rectilinear Steiner trees and queue theoretic deterministic supply/demand server satisfaction over this? Actually, a decent, general floorplanner that was not restricted to chips would be enough

I spent highschool in schizoid withdraw and can't do algebra because of it.
I've always studied science but I would like to get to the theoretical side.
I've started learning introductory set theory and logic and it comes easy. I would like to get to the point where I am proficient enough in network and system theory to research theoretical ecology m. Tell me what I need to study to reach my goals. I'm fine with intense learning as long as I don't need prerequisites.
are informal graphs worth a shit beyond conceptualization?
I ate 14 grams of magic mushrooms and I could see network dynamics. Green, flowing graphs of Trophic interactions and ecological succession. What's up with that?

Way to ruin the thread moron.

What are some engineering applications? Should I bother learning it?

Why is your field such a meme?

Automatically designing stuff, ie doing your job

How do people start to come up with algorithms for graphs? I remember learning algorithms for maximum flow and things like FFA seemed so abstract and unintuitive.

...

What's a fast algorithm to get a weighted maximum matching of a bipartite graph?

>FFA seemed so abstract and unintuitive.

While(I can pump more)
-> pump more

What's unintuitive?

That's a little vague. Please elaborate further.

There is software out there that takes loads and dimensional constraints from the user and algorithmically designs and analyses potential solutions.
The structures generated by this sort of algorithm are funky and organic-looking.
Main problem currently is manufacturing, a "perfect" design may not always be possible to produce by usual methods. With additive manufacturing however this can change...

And how is that related to graph theory? I'd imagine it being some sort of genetic algorithm, or calculus of variations.
[Want to know more]