Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2009-01-11 08:18:52

freddogtgj
Member
Registered: 2006-12-02
Posts: 54

Algorithmic Graph Theory Help

Consider the graph G defined as follows.  The vertex set V(G) consists of all triples

with each
equal to 0 or 1.  The edge set E(G) consists of all pairs of triples
such that there is exactly one number i with
.

How many vertices does G have? How many edges does G have?


Thanks in advance!
Sorry for the maths looking like superscript compared to the rest of the text.  Anyone like to tell me how to deal with that will also be great.

Last edited by freddogtgj (2009-01-12 01:42:52)

Offline

#2 2009-01-11 13:04:31

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Algorithmic Graph Theory Help

What part of the problem are you having trouble with?


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#3 2009-01-12 01:46:06

freddogtgj
Member
Registered: 2006-12-02
Posts: 54

Re: Algorithmic Graph Theory Help

Well, the stumbling block for me is the vertex part.  I'm not quite sure how the vertex points are meant to be read.  It says that the set consists of all triples with each x_i equal to 0 or 1, but i thought that a vertex can only be defined by one x_i rather than a triple.  Am i wrong?

Offline

#4 2009-01-12 09:07:44

mathsmypassion
Member
Registered: 2008-12-01
Posts: 33

Re: Algorithmic Graph Theory Help

You are working in 3D. So the coordinate system has three axes.
Because 2×2×2 = 8 you have 8 vertices in V(G).

000,001,011,010,100,110,101,111

Using the definition of the edge, for example 000, 111 does not represent one because thre are 3 different numbers between them not 1 as required but 000 , 001 is an edge.
There are a few others, try to find them.

Offline

#5 2009-01-14 08:22:48

freddogtgj
Member
Registered: 2006-12-02
Posts: 54

Re: Algorithmic Graph Theory Help

Ok i see mathsmypassion.  Now does that mean the number of edges are 12?

Offline

#6 2009-01-14 08:47:06

mathsmypassion
Member
Registered: 2008-12-01
Posts: 33

Re: Algorithmic Graph Theory Help

12 sounds good for me.

Offline

Board footer

Powered by FluxBB