Graphs (MWA)

Question 1

Graph

Answer 1

finite set of vertices/nodes connected by arcs/edges

Question 2

Simple graph

Answer 2

Graph w no loops or repeated edges

Question 3

Loop

Answer 3

edge that links a vertex 2 itself

Question 4

Connected graph

Answer 4

Graph where every vertex li is by a network of edges

Question 5

Disconnected graph

Answer 5

Graph where vertices r linked w 2 distinct networks of edges

Aka where looks like 2 different graphs but apparently supposed 2 b one whole graph

Question 6

Complete graph

Answer 6

Graph where every vertex r linked 2gether by an edge (can’t have multiple edges)

Question 7

Subgraph

Answer 7

Part of a graph that comes from a main one

Question 8

Planar graph

Answer 8

Graph that can b drawn w/o any edges crossing

Question 9

Degree of a vertex

Answer 9

No. Edges at the vertex

Question 10

Handshaking theorem

Answer 10

Sum of degrees = 2 x (edges)

Aka always even

Question 11

If there’s an odd degree of vertices

Answer 11

There r an even no. Of nodes

Question 12

Isomorphism

Answer 12

2 graphs have same structure

Aka all their nodes have same degree

Question 13

Digraph

Answer 13

Graph where edges have a particular direction

eg one way street

Question 14

Bipartite graph

Answer 14

Vertices form 2 distinct sets and can’t link vertices w/in same set

Question 15

Kr,s

Answer 15

Notation 4 bipartite graphs

r= no. Vertices in set 1
s= no. Vertices in set 2

Question 16

Walk

Answer 16

Sequence of edges taken From one vertex 2 another

Question 17

Trail

Answer 17

walk w no repeated edges in any directiob

Question 18

Path

Answer 18

Trail w no repeated edges (but 1st vertex can b the last)

Question 19

Cycle

Answer 19

Journey that starts and ends w/i any intersections

Question 20

Closure

Answer 20

When walk/path/trail finishes at starting vertex (can only happen when every vertex has even degree)

Question 21

Eularian trail

Answer 21

Closed trails where every edge is used just once

So traversable (aka an draw in one line) and all vertices must have even degree

Question 22

Semi eularian graph

Answer 22

Non closed trails

So have 2 odd vertices and only traversable if start and end w the 2 off vertices

Question 23

Hamiltonian cycle

Answer 23

Closed path the passes every vertex of a graph

Question 24

Hamiltonian graph

Answer 24

Graph where has a Hamiltonian cycle

Question 25

Tree

Answer 25

Connected graph w no cycles

Question 26

Spanning tree

Answer 26

Sub graph that has all the vertices of original graph but is a tree in its own right