Re: Graphs and reducibility(or something like that)

On Jul 21, 12:36 am, "Jon Slaughter" <Jon_Slaugh...@xxxxxxxxxxx>
wrote:
"Proginoskes" <CCHeck...@xxxxxxxxx> wrote in message
news:1184985789.069875.300990@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

On Jul 20, 6:49 pm, "Jon Slaughter" <Jon_Slaugh...@xxxxxxxxxxx> wrote:
I'm trying to simplify a network of electrical components and I'm curious if
theres any way to do this.

The network is equivalent to a graph but each edge consists has a "weight"
to it that is a function. Every edge has a similar function that "looks" the
same. Some nodes are known values while others are not.

The function is actually a linear differential equation with constant
coefficients.

For example, I might have something like

+
/\
Z2 Z3
/ \
+--Z1--+

Where Z1, Z2, Z3 are differential equations.

In reality the graph is equivalent to a system of differential equations and
there are unknowns that exist which each branch and/or at some nodes.

I can convert the differential equations into algebraic equations by taking
the laplacian as one method but it still involves solving a large system.

I'm more interested in using the fact that each edge/branch is identical to
every other one except for some basic constants.

In essence I think I can treat each branch with a weight as a vector where
the elements of the vector are the coefficients of the DE.

so for example, I might have as a function L(t;....) = c*dV1/dt + a*V2 - b*V3

and so I could treat that as a vector like (a,-b,c). Every branch will just
have different coefficients in the function L but all of the same "form". I
feel that I could somehow use this to my advantage at simplifying the
graph/system. (Although I think the size of the vector grows exponentially
based on the size of the graph)

Is there anything I can do to simplify my problem? Maybe there are some
results in graph theory(I think this is where the problem comes from) that
can help? I'm actually wondering if there is some recursive way to simplify
the elements. Most of the "vectors" will only have non-zero elements for
those that represent coefficients around its branch.

In any case just looking for some ideas,

But where are you using the fact that you have a graph? How does the
edge uv related to the vertex u, for instance? And what kind of
structure do you have? For instance, do the differential equations
along a cycle satisfy some law like Kirchoff's?

I don't have a graph?

http://en.wikipedia.org/wiki/Glossary_of_graph_theory

A graph is just a set of verticies and edges which some relation that maps
pairs of verticies to edges? If thats the case then I definitely have a
graph.

Oh, I see now. You are given an electrical network, which gives you
the graph.

In any case, when I have all these weights there is an operation to combine
them in a specific way.

Suppose

W(Ni,Nj) is the "weight" of the edge NiNj which, for this problem, is
generally some linear differential equation.

Then we know that

sum(I(W(Ni,Nj)),j \in Q) = 0

This is kirchoffs current law which just says that the sum of the currents
entering a node is 0.

There is another law which states that the sum of the current around a
loop must add up to 0.

I is a "function" that maps the weight into its
equivilent current and Q is the set of indecies for nodes that are adjacient
to Ni.

We also would have something like

V(Ni) - sum(V(Nj),j \in Q) = 0

where V maps a node to a voltage and Q is an ordered closed list of
adjacient nodes. This would be kirchoffs voltage low.

(I'm kinda making up those equations as I go so they might not be totally
right)

I think I can see at least the general direction you're heading.

Whatever the laws are, they give you a system of equations. Kirchoff's
two laws will state that these equations are related to each other,
and so your system will be redundant. The redundancies, along the
edges, will be determined by the cycle-space of your graph G (a cycle
is basically a loop; you don't repeat vertices or edges until you're
done with walking around a cycle).

You can find the cycle space by setting up a particular matrix and
looking for a basis for its null space.

But I think the main point here is that what I ultimately have is just
weights that are differential equations and inside those equations I have
all the info about the electronic aspect of the graph but abstractly its
just a graph with weights and I should be able to simplify it.

Whats really going on is that I have the weight function W(Ni,Nj) =
(V(t,Ni) - V(t,Nj))/Z_NiNj(t,N1,...,Nn;a1..am)

And you can think of this as ohms law. It essentially defines a current on
the edge NiNj. Then of course I must have sum(W(Ni,Nj)) = 0 for all Nj with
common vertext Ni. This is kirchoffs current law.

Maybe I'm starting not to make sense though. The idea is simply to
generalize the case for resistors.

Basically: "If you put other gadgets into the circuit (capacitors,
relays, whatever), you have other rules which determine how the
current flows through them", which are given by the differential
equations? And you're trying to simplify your system.

if I have some graph of resistors then what I really have is a linear
algebraic system of equation. Each edge creates an equation. The system is
related to the graph. Change the graph and change the system.

Infact what we have is V(Ni) - V(Nj) - RNiNj*INiNj = 0 for each edge and
sum(NiNj) = 0 for each node Ni where the sum is over adjacient nodes to Ni.

It seems I end up having to have an extra structure though that exists on
the graph. Maybe I need to think it out a little more.

Well, hopefully I've thrown out some useful ideas here, or failing
that, the sort of questions to ask. 8-)

--- Christopher Heckman

.

Relevant Pages

  • Re: Graphs and reducibility(or something like that)
    ... results in graph theory ... Wis the "weight" of the edge NiNj which, for this problem, is ... This is kirchoffs current law which just says that the sum of the ... weights that are differential equations and inside those equations I have ...
    (sci.math)
  • Re: copyright for combinatorial entities
    ... could you ever "create" a graph, ... In US American law copyright pertains to authorship ... blocking the publication of an adjacency matrix ... to your approval for its creation. ...
    (sci.math)
  • Re: Graphs and reducibility(or something like that)
    ... Where Z1, Z2, Z3 are differential equations. ... In reality the graph is equivalent to a system of differential equations ... In essence I think I can treat each branch with a weight as a vector ... This is kirchoffs current law which just says that the sum of the currents ...
    (sci.math)
  • Yet another square root law?
    ... Ignore for the moment that I do not think this is what the graph is ... I just find it interesting to find yet another square root law ... The first such square root law I encountered was Tjaden and Flynn's ... I have conjectured that, in 3D integration, the appropriae ...
    (comp.arch)
  • Re: Open Path TSP ...
    ... the Hamilton path instead of Hamilton cycle and strickly constrained by ... If you take your problem on graph G and start and end vertices u,v, ... Any cycle solution on G+x will have to contain the edges and ... and so the weight of your hamiltonian path on G will be the weight of ...
    (sci.math.research)
Loading