Answering questions about graph theory

Recommend a book about graph theory as a whole pls?
Also, is there an algorithm for minimum coloring?

>>8924207
1) Bondy-Murty is one of my favorites. Diestel is also good. Both of those have pdfs online as well.

2) It depends what you mean by "algorithm" and what you mean by "coloring". There is no efficient algorithm for coloring the vertices of a general graph with a minimum number of colors so that adjacent vertices don't receive the same colors, because this problem is NP-complete. However, there are numerous "inefficient" algorithms for this type of graph coloring, e.g. brute force, or using integer programming. These types of algorithms work for moderately-sized graphs.

There are also efficient algorithms for minimum colorings of graphs with special structure, e.g. bipartite graphs, perfect graphs, etc. Those (at least in theory) work for large graphs of those families.

>>8925083
also, if you don't need your coloring to necessarily use the smallest possible number of colors, you can use a heuristic like greedy coloring or Brelaz's heuristic; the latter gives a minimal (but not necessarily minimum) coloring.

>>8923907
What's the fastest way to check for graph isomorphism?

>>8925165
Babai has recently claimed it's possible in quasipolynomial time, that's the best theoretical algorithm for it. see this video for his lecture on it: https://www.youtube.com/watch?v=S5ovzZJ8vI8

As far as I know, his research is not completely verified yet, and certainly not implemented in practice, but it's the most promising result on isomorphism in the last few decades.

If you care about practical algorithms, then there are decent implementations in all the popular symbolic algebra systems like mathematica, sage, etc.

>>8925213
I gotta go fast, how do I implement thay algorithm?

Chemfag here. No idea what graph theory is.

What is graph theory? Can you explain it in a way that is easy to understand and possibly use an ordinary example?

>>8923907
you into spectral?

>>8926687
For a fast implementation, check out nauty; it's one of the best: http://www3.cs.stonybrook.edu/~algorith/implement/nauty/implement.shtml
>>8926752
you have a bunch of nodes and a bunch of edges that connect the nodes. That's a graph in the abstract sense.
Graphs are useful because they can be used to model various things. For example, you can have a graph where the nodes are people, and an edge exists between two nodes whenever the two people know each other. That's a social network graph.
In chemistry, you might construct a graph as follows: the nodes correspond to the atoms of a compound, and edges correspond to chemical bonds.
The theory of graphs deals with various problems defined on graphs. The tl;dr version is this: first you find out if your problem is easy or hard (in a complexity theory sense). Then, if your problem is hard, you focus on developing bounds, structural results, heuristics, etc. If your problem is easy, you focus on developing efficient algorithms and implementing them.

>>8926780
It's not my main specialty, but I do have a couple papers on spectral so I can at least point you in the right direction if you have a question

>>8925083
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?

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

>>8926879
Here's a 2008 edition of Bondy & Murty, it's a bit more polished than the 1985 edition: https://www.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

File: test (1).png (715KB, 779x1011px) Image search: [Google]

715KB, 779x1011px

>>8923907
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.

>>8927262
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.

File: chen_class.png (92KB, 532x391px) Image search: [Google]

92KB, 532x391px

>>8927300
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.

>>8927308
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.

>>8927308
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.

>>8923907
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?

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

>>8927327
found the PDE guy

>>8927328
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?

>>8927330
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

>>8923907
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.

File: Untitled.png (6KB, 533x292px) Image search: [Google]

6KB, 533x292px

>>8927380
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?

>>8927396
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.

>>8927407
*bijection

File: Untitled.png (3KB, 380x292px) Image search: [Google]

3KB, 380x292px

>>8927407
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?

>>8927461
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.

File: 1492374527528.jpg (39KB, 480x479px) Image search: [Google]

39KB, 480x479px

reduce vertex cover to set cover right now

>>8927474
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

>>8927479
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.

>>8927500
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.

>>8927523
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.

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

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

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

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

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

>>8927773
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

>>8927745

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.

File: 00312843_medium.jpg (17KB, 188x300px) Image search: [Google]

17KB, 188x300px

>>8926752
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.

File: raven.gif (2KB, 253x179px) Image search: [Google]

2KB, 253x179px

>>8927811
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?

>>8927798

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.

>>8927811
Thanks anon, I'll check out those resources!

>>8927893
Care to give more info on that bird?

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

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

>>8927362
>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.

>>8928060
a heuristic to do what?
>>8928062
Probably, I'm not aware of any useful applications of zeta functions in graph theory
>>8928178
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:
http://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

>>8928198
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

>>8929536
>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

https://en.wikipedia.org/wiki/Hadwiger%E2%80%93Nelson_problem
https://en.wikipedia.org/wiki/De_Bruijn%E2%80%93Erd%C5%91s_theorem_(graph_theory)

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

>>8929562
Enough of your piggot oinkery

>>8923907
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?

>>8929562
>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

>>8929583
You seem a little flustered... piggot.

>>8923907
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?

>>8923907
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

>>8923907
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?

>>8929689
Way to ruin the thread moron.

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

Why is your field such a meme?

>>8929896
Automatically designing stuff, ie doing your job

>>8923907
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.

File: image.png (7KB, 224x225px) Image search: [Google]

7KB, 224x225px

>>8929857

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

>>8930656
>FFA seemed so abstract and unintuitive.

While(I can pump more)
-> pump more

What's unintuitive?

>>8930654
That's a little vague. Please elaborate further.

>>8931205
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...

File: SpmKoAE.jpg (48KB, 853x480px) Image search: [Google]

48KB, 853x480px

>>8931242
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]