Difference between revisions of "MCSN Tuesday, 13-Sep-11"
(→Graph theory (Wilson ch. 1)) |
(→Graph theory (Wilson ch. 1)) |
||
| Line 23: | Line 23: | ||
* multiple edges, loops | * multiple edges, loops | ||
* simple graph | * simple graph | ||
| − | * walk (alternating sequence of vertices and lines) | + | * walk (alternating sequence of connected vertices and lines) |
| − | * path (alternating sequence of vertices and lines, such that the vertices don't repeat) | + | * path (alternating sequence of connected vertices and lines, such that the vertices don't repeat) |
* '''E'''ulerian graph (contains a walk containing every '''e'''dge once, and returning to starting point) | * '''E'''ulerian graph (contains a walk containing every '''e'''dge once, and returning to starting point) | ||
* Hamiltonian graph (contains a walk containing every vertex once, and returning to starting point) | * Hamiltonian graph (contains a walk containing every vertex once, and returning to starting point) | ||
Revision as of 20:34, 12 September 2011
Contents
Today's assignment
Social structure. Read Preface, p. 1, and sections 1.1 to 1.3.2. Graph theory exercise due (distributed by email) - submit answers via the Moodle (see above for instructions regarding network diagrams). Brainstorm some MCSN examples with research questions.
Course mechanics
Pajek
- installations ok?
- Issues with Wine?
- Got data?
Graph theory (Wilson ch. 1)
- vertex
- edge,arc
- degree
- graph, digraph
- multiple edges, loops
- simple graph
- walk (alternating sequence of connected vertices and lines)
- path (alternating sequence of connected vertices and lines, such that the vertices don't repeat)
- Eulerian graph (contains a walk containing every edge once, and returning to starting point)
- Hamiltonian graph (contains a walk containing every vertex once, and returning to starting point)
- connected and disconnected graphs
- tree (only one path between each pair of vertices)
- planar graph
- counting graphs
- isomorphic graphs, and difference
- how many different simple graphs can you create with a fixed number of vertices? (1,2,3,4)
- Wilson ch.1 questions
ESNAP reading
- Sections 1.1 to 1.3.2.
