Graph Theory - 2017-08-04

GFauxPas

15:44

Sup :)

It's a nice problem, difficult but tractable

I'm the only pure mathematician there, I think that's why they wanted me, possibly a different perspective from a programmer

So it's like this

It's the optimization of a circuit board

so there aren't nodes added or removed once the circuitboard is made

On the board I'm going to put 32 nodes, each that can connect to up to 6 switches

24 switches, each that can connect to up to 8 nodes

let me draw something

actually theres a site where you can make graphs, lets see if I can find it

Semiclassical

sure, lemme know when you've gotten it

GFauxPas

can you view this

or do you need to be logged in

Semiclassical

I'm not seeing anything.

GFauxPas

thought so, let me download the image

see it?

Semiclassical

there we go

sure, that's fine.

GFauxPas

15:59

okay, so my first problem was, that a graph doesnt allow for two different types of nodes

but then I found out about bipartite graphs

so we can do that

Semiclassical

can the nodes be connected to each other?

ah, so it is bipartite.

GFauxPas

no

nor the switches

Semiclassical

yeah.

GFauxPas

so the thing has to be connected

Semiclassical

so you've got a bipartite graph; let's call those red/blue

GFauxPas

16:01

also, there's no advantage to having multiplicity in the connections. if a packet is being sent from node i to node j through switch k, having it connected twice won't help any

but...

Semiclassical

where there should be 32 red vertices, each with degree at most 6, and 24 blue vertices, each with degree at most 8

GFauxPas

notice that there are exactly two paths from N1 to N3

exactly

Semiclassical

Right.

GFauxPas

Geogebra is probably better than this website actually, but this is good of rnow

so the problem is,

to design a graph that maximizes there being twoo ways to get between any two nodes

if there's only one path, if the path is busy, the packets have to be rerouted in an inefficient way

so we want redundency

but the benefit from going from one path to two paths is much greater than the boost from going from two paths to three

Semiclassical

So you want to ensure that there's at least two paths between all nodez

GFauxPas

16:07

right. but my boss is pretty sure there isn't a way to have two paths between EVERY twos nodes

in which case the problem is to find the way that has the most

Semiclassical

Hmm

Probably you'll want to study a smaller version of the problem to get some intuition

GFauxPas

probably a good idea

Semiclassical

Do the lengths of the paths matter?

GFauxPas

no

do you know any good software to make colored graphs by the way

I'll Google it later

so my starting point is using adjacency matrices, there are nice theorems about those

if I have (Node, Switch) x (Node, Switch):

Semiclassical

The problem I see with adjacency matrices is that, if you want paths, you want powers of the adjacency matrix

GFauxPas

16:13

$\begin{bmatrix} NN & NS \\ SN & SS\end{bmatrix}$.

then $NN = SS = 0$ and $NS = SN$, which is good

Semiclassical

in which case you seem stuck with the path length

Mm block matrices

GFauxPas

right, well, it's a starting point

Semiclassical

The matrix exponential exp(t A) may be a good object as well

Since that'll carry info about all powers of the adjacency matrix A

ill also point out that Mathematica has some graph functionality

In particular, it's got a FindPath command for finding simple paths between vertices

GFauxPas

I'll have to ask my boss if he can get me Mathematica (or Maple?)

so I should read about the matrix exponential?

I got a book "introductory combinatorics" by Kenneth P Bogart, but only part of it is on graphs and matricesx

Semiclassical

Matrix exponential is pretty quick

GFauxPas

16:20

I know the definition

$\displaystyle e^A = \sum_{n=0}^\infty \frac 1 {n!} A^n$, right?

Semiclassical

Right.

GFauxPas

oops, $NN = 0$ and $SS = 0$ but I shouldnt say $NN = SS$ because theyre different sizes

but you probbaly got what I meant

do you have a good source?

textbook or website

Semiclassical

not off the top of my head

GFauxPas

and $e^A$ exists for any matrix of numbers, right?

square

Semiclassical

Right.

I guess you also only care about odd powers of A as well

GFauxPas

16:23

one problem with the adjacency matrix is that it counts paths from a vertex back to itself

why only odd powers?

but it's a starting point

Semiclassical

Should've been even. The reason is that any path of odd length will connect a switch to a node

And that's not your interest

GFauxPas

aahh nice

but I have to read up on adjacency matrices etc because I dont know anything about them, I just heard of them yesterday

my coworker sent me a project he used adjacency matrices for with a previous project, I havent looked at it yet

my book also has a thing that I dont know is useful

matrix multiplication of adjacency matrices where the sum is given as

$1 + 1 = 1 + 0 = 0 + 1 = 1$, $0 + 0 = 0$

Semiclassical

In fact. Note that the meaning of $A^2$ is that tracks the number of paths of length two.

GFauxPas

where the sum of two numbers*

so the dot product of a row and a column is either 1 or 0

Semiclassical

Right.

Furthermore, you can think of A^2 as itself the adjacency matrix of a graph.

GFauxPas

16:31

because we only care about even powers?

Semiclassical

namely: make a copy of all your red vertices, and draw an edge between them if there's exactly one blue vertex between them.

right.

(each vertex is connected to itself by definition, so there's some redundancy here)

GFauxPas

reminds me of transitive closure

Semiclassical

Hmm. The problem with this line of thinking is that the constraints you're faced with are at the level of A itself.

GFauxPas

except you delete the first relation

so $R^T \setminus R$ or something

Semiclassical

something like that.

GFauxPas

16:34

this is harder than any graph theoretical problem Ive done before, but he has most of the people in the department working on it. he wants it done by September if possible

"most of the people" being like 4, its smal

4 besides me

Semiclassical

Constraint should be that each of the 24 columns of S should sum to 8, and each of the 32 columns of N should sum to 6. (S and N should both be symmetric)

GFauxPas

might be harder than any problem ive done before period actually :P

Semiclassical

Oh. And all matrix elements are 0 or 1, of course.

GFauxPas

theres anojther constraint that i may not have to worry about for a while

he wants there to be two sub-boards connected to each other, each with 16 red and 12 blue, and the subboards should be identical

i think that makes it easier rather than harder

Semiclassical

huh.

that should correspond to some additional structure on the adjacency matrix

GFauxPas

16:40

but everyone is telling me to start with a much smaller graph when starting this problem

Semiclassical

neat problem.

GFauxPas

it is :)

I hope it isnt too hard for me

Semiclassical

one possible approach to get a feel for this is to somehow randomly generate a possible graph. that may give a sense of how good a 'typical' graph wilil do

GFauxPas

writing code to do that is something I'll have to do anything in this problem, I'm going to need to do matrix algebra

Semiclassical

right.

GFauxPas

16:42

probably going to use R

since thats the language I know the best

Semiclassical

You may be able to find some open source tools for graph analysis.

GFauxPas

R's packages are all open source :)

so im sure there are

Semiclassical

right. main issue is that the word 'graph' is so overloaded.

GFauxPas

is the adjacency matrix the standard way to turn a graph into a matrix? are there other ways?

Semiclassical

you're not interested in plots :P

GFauxPas

16:43

lol I know!

its sometimes hard to search for

you have to hope people include the term "graph theory" somewhere

Semiclassical

I think there are others. adjacency matrix is nice when there's more nodes than edges.

GFauxPas

"lower more" is a typo Im sure

"lot more"?

Semiclassical

it might help to include "vertex" and "edge" as keywords

woops

because then the matrix is sparse, etc.

GFauxPas

in general, thank you so much for helping me Semi :) an open thank you

Semiclassical

np. seems like an interesting problem.

GFauxPas

16:47

is it true that when matrix algebra was first developed, people didn't think it would have any practical application?

Semiclassical

sounds right.

GFauxPas

I heard that somewhere

Semiclassical

i know that Heisenberg reinvented matrix multiplication while developing matrix mechanics.

so it evidently wasn't well-known at the time.

Semiclassical

18:09

Actually, just noticed a further constraint. To restate from earlier: 32 nodes connected to at most 6 switches each, and 24 switches connected to at most 8 nodes each

so there's at most 32*6=172 edges coming from the nodes, and 24*8=172 edges coming from the switches...oh. it is compatible.

never mind!

(this is 172 edges assigned out of 32*24=768 possible edges.)

Semiclassical

18:29

Played around with it some more. One thing I'm finding with random generation already: it's really hard to find a graph with more than 160 edges which satisfies the desired conditions.

Semiclassical

19:31

@GFauxPas I allowed myself to get distracted by this stuff this afternoon and came up with some good results. Lemme know when you're around.

Transcript for

$Mathematics$ Graph Theory