Graph theory Flashcards Preview

Calculus > Graph theory > Flashcards

Flashcards in Graph theory Deck (30)
Loading flashcards...
1
Q

adjacent

A

two vertices connected by and edge

2
Q

incident

A

the edge e=(y,v) is incident with u and v

3
Q

handshaking theorem undirected

A

2E = sum(degrees of v)

4
Q

handshaking theorem Directed graphs

A

E= degree outv = degree inv

5
Q

chromatic number of Kn

A

complete n

6
Q

chromatic number of Cn

A

circle 3 odd, 2 even

7
Q

Wn chromatic

A

wheel 3 odd 4 even

8
Q

Sn

A

star graphs 2

9
Q

Bipartite

A

iff vertices of G can be colored by 2 or fewer colors

iff every circuit has even length

10
Q

Euler circuit

A

a simple circuit containing every edge of G

11
Q

Euler Path

A

a simple path containing every edge of G

12
Q

how to tell if it has a Euler circuit

A

Every vertex must have an even degree

13
Q

how to tell if it has a Euler path

A

has exactly 2 vertices of odd degree rest must be even

14
Q

Hamiltonian circuit

A

a circuit covering each vertex exactly once

15
Q

Planar

A

can be drawn in the plane without crossing edges

16
Q

eulers formula for connected planar graphs

A

V-E+R =2

17
Q

Edge bound for connected planar simple graphs

A

E<=3V-6

18
Q

Edge bound for connected planar simple graphs without triangles

A

E<=2V-4

19
Q

Kurtowskis theorem

A

G is nonplanar iff it contains a subgraph K5 or K3,3 cant bge greater than 5 or 3

20
Q

4 color theorem

A

for planar graphs the chromaic number cant be more than 4

21
Q

height of a tree

A

counted by edges for discrete

22
Q

spanning tree

A

is a sugraph of G that contains every vertex of G

23
Q

how to tell if a simple graph is connected

A

a simple graph is connected iff it has a spanning tree.

spanning rees have n-1 edges wehre n is averitce

24
Q

minimum spanning tree

A

for weighted graphs, a tree with the minimum weight

25
Q

Prims algorithm

A

Start with edge of minimum weight. pick next largest that is incident to the edge you have, get all the vertices wtihout making a circuit

26
Q

Krustals algorithm

A

CHoose the edges that are minimum. keep moving up in weight until all vertices are connected with no circuits

27
Q

Reflexive

A

loops at every vertex

1s on the main diagonal

28
Q

symmetric

A

No single edges between vertices

symmetric about main diagonal

29
Q

transitive

A

any directed path of length 2 must have a connecting path

30
Q

equivalence.

A

reflexive, transitive, and symmetric