Transcript Adjacency Matrices Power point

Warm up 10-22-2010
1.
2.
Mr. Euler and Mr. Hamilton sit down one day to
invent a game. They call their new game
“baseball.” They argued about whether it was
more important to run on the base paths or to
touch the actual bases. Who ended up winning
the argument?
A “circuit board” is an electronic piece of
equipment involved in all kinds of technology.
The electricity that passes through a circuit
board starts at the power source and travels
through the circuit back to the power source.
How come we don’t call it a “path board?”
Vertex Edge Graphs Day 3:
Adjacency Matrices
Graphical
An adjacency matrix is a ___________
way of
displaying the data shown in a
Vertex Edge Graph
____________.
Consider the following social network below.
What could it represent?
Phone
Calls, Texts, letters, emails, Facebook posts, conversations, etc.
____________________________
Lisa
Alex
Debra
Steph
Justin
J.C.
What do the arrows represent in this vertex edge
graph?
Some type of connection or contact.
________________
And arrow towards a person means what?
They received a communication.
________________
An arrow away from a person means what?
They sent a communication.
________________
An arrow on both ends means what?
They both received and sent a communication.
________________
Vertex Edge Graph vs. Adjacency Matrix
The vertex edge graph is convenient to use
when comparing two pieces of information.
An adjacency matrix is more useful when
comparing all the information or when
comparing several parts at once.
First you must define your
values:
►1
in a row means
A connection was made/sent to the person in the column
______________________________________
► 0 in a row means
No connection was made/sent to that person.
______________________________________
► 1 in a column means
That person received a communication.
______________________________________
► 0 in a column means
No communication was received.
______________________________________
Now fill in your Adjacency Matrix
Lisa
Steph
Justin
J.C.
Debra
Alex
Total
Lisa
0
1
1
0
1
1
Steph
1
0
1
0
1
0
Justin
0
0
0
1
1
1
J.C.
0
0
1
0
0
0
Debra
0
0
0
1
1
0
Alex
0
0
0
1
1
0
Total
1
1
3
3
5
2
4
3
3
1
2
2
15
What do these totals tell us?
The totals of the rows are the number of messages sent. The
totals of the columns are the number of messages received.
Answer the following questions.
Answers will vary.
Who is the most “outgoing” or “outspoken/written?”
_____________________________
►
Who is the “most popular?”
_____________________________
►
Who is the “least popular?”
_____________________________
►
Who is the most “introverted?”
______________________________
►
Example 2
Given this tournament graph, make an
adjacency matrix to determine 1st, 2nd, 3rd,
Cal
Tres
Justin
Al
and 4th place.
Cal
Justin
Tres
Al
Cal
0
0
1
0
1
Tres
1
0
1
0
2
Justin
0
0
0
0
0
Al
1
1
1
0
3
Al took 1st, Tres was 2nd, Cal was 3rd, and Justin was 4th.
Total
Example 3
Given this tournament graph, made an adjacency matrix to
determine 1st, 2nd, 3rd, and 4th place.
Bo
Justin
Dan
This one is a little
different, we don’t
know the clear winner
without thinking a bit.
You can still make
your matrix and find
the row sums.
Total
Bo
Kat
Justin
Dan
Bo
0
0
1
0
1
Kat
1
0
0
1
2
Justin
0
1
0
0
1
Dan
1
0
1
0
2
Kat
►
►
►
►
2
The row sums tells us we can have ______
winners, they are
Dan
Kat
_________
or _________.
Bo
Now we need to list the Hamilton Paths (there are five)
BJKD
KDBJ
DJKB
___________,
_________
and ________
Justin
Which one matches the matrix the best? Why ?
According to our matrix, Bo and Justin have to finish 3rd and 4th while Kat and
Dan have to finish 1st and 2nd. KDBJ most closely matches that situation.
Total
Bo
Kat
Justin
Dan
Bo
0
0
1
0
1
Kat
1
0
1
0
1
0
0
0
1
1
0
0
2
1
2
Justin
Dan
Kat
Dan
Summary: An adjacency matrix is used to…
Homework: Adjacency Matrix w/s