×
Log in to StudySoup
Get Full Access to Stony Brook U - AMS 301 - Class Notes - Week 3
Join StudySoup for FREE
Get Full Access to Stony Brook U - AMS 301 - Class Notes - Week 3

Already have an account? Login here
×
Reset your password

STONY BROOK U / Intro to Applied Statistics / STA 301 / What is a connected graph without circuits?

What is a connected graph without circuits?

What is a connected graph without circuits?

Description

.lst-kix_7sl378fhtstc-1 > li:before{content:"- "}ul.lst-kix_bvalbyiyltal-6{list-style-type:none}ul.lst-kix_bvalbyiyltal-7{list-style-type:none}ul.lst-kix_bvalbyiyltal-4{list-style-type:none}ul.lst-kix_bvalbyiyltal-5{list-style-type:none}ul.lst-kix_bvalbyiyltal-2{list-style-type:none}ul.lst-kix_bvalbyiyltal-3{list-style-type:none}.lst-kix_7sl378fhtstc-0 > li:before{content:"- "}ul.lst-kix_bvalbyiyltal-0{list-style-type:none}ul.lst-kix_bvalbyiyltal-1{list-style-type:none}.lst-kix_7sl378fhtstc-5 > li:before{content:"- "}.lst-kix_83v58aijjsiw-6 > li:before{content:"- "}.lst-kix_7sl378fhtstc-3 > li:before{content:"- "}.lst-kix_7sl378fhtstc-7 > li:before{content:"- "}.lst-kix_83v58aijjsiw-8 > li:before{content:"- "}.lst-kix_7sl378fhtstc-2 > li:before{content:"- "}.lst-kix_7sl378fhtstc-6 > li:before{content:"- "}.lst-kix_83v58aijjsiw-7 > li:before{content:"- "}.lst-kix_7sl378fhtstc-4 > li:before{content:"- "}.lst-kix_83v58aijjsiw-0 > li:before{content:"- "}.lst-kix_bvalbyiyltal-6 > li:before{content:"- "}.lst-kix_bvalbyiyltal-5 > li:before{content:"- "}.lst-kix_bvalbyiyltal-3 > li:before{content:"- "}.lst-kix_83v58aijjsiw-5 > li:before{content:"- "}.lst-kix_bvalbyiyltal-4 > li:before{content:"- "}.lst-kix_83v58aijjsiw-4 > li:before{content:"- "}.lst-kix_83v58aijjsiw-3 > li:before{content:"- "}ul.lst-kix_bvalbyiyltal-8{list-style-type:none}.lst-kix_83v58aijjsiw-2 > li:before{content:"- "}.lst-kix_bvalbyiyltal-7 > li:before{content:"- "}.lst-kix_83v58aijjsiw-1 > li:before{content:"- "}.lst-kix_bvalbyiyltal-8 > li:before{content:"- "}ul.lst-kix_83v58aijjsiw-6{list-style-type:none}.lst-kix_bvalbyiyltal-1 > li:before{content:"- "}ul.lst-kix_83v58aijjsiw-7{list-style-type:none}ul.lst-kix_83v58aijjsiw-8{list-style-type:none}ul.lst-kix_7sl378fhtstc-0{list-style-type:none}ul.lst-kix_7sl378fhtstc-1{list-style-type:none}ul.lst-kix_7sl378fhtstc-2{list-style-type:none}ul.lst-kix_7sl378fhtstc-3{list-style-type:none}.lst-kix_bvalbyiyltal-2 > li:before{content:"- "}ul.lst-kix_7sl378fhtstc-4{list-style-type:none}ul.lst-kix_7sl378fhtstc-5{list-style-type:none}ul.lst-kix_7sl378fhtstc-6{list-style-type:none}ul.lst-kix_7sl378fhtstc-7{list-style-type:none}ul.lst-kix_7sl378fhtstc-8{list-style-type:none}.lst-kix_bvalbyiyltal-0 > li:before{content:"- "}ul.lst-kix_83v58aijjsiw-0{list-style-type:none}ul.lst-kix_83v58aijjsiw-1{list-style-type:none}ul.lst-kix_83v58aijjsiw-2{list-style-type:none}ul.lst-kix_83v58aijjsiw-3{list-style-type:none}.lst-kix_7sl378fhtstc-8 > li:before{content:"- "}ul.lst-kix_83v58aijjsiw-4{list-style-type:none}ul.lst-kix_83v58aijjsiw-5{list-style-type:none}

Section 3.1If you want to learn more check out What are the three primary agents of metamorphism?

If you want to learn more check out What is a process used to treat phobias?
We also discuss several other topics like What is pseudorandom?

Tree - a connected graph without circuitsIf you want to learn more check out Discuss what chargaff's rule is about.

We also discuss several other topics like What idea refers to a communal group of actors who believed in communism and revealing what the bottom of the social scale was like?

Theorem 1: if T is connected, these are equivalent (imply each other)

  • T has no circuits
  • If a is a node rh for every node x there exists a unique path between a and y.
  • For every noe pair x and y, there exists a unique path between x and y
  • T is minimally connected. Removing an edge and means T is no longer connected

We also discuss several other topics like mdu4003 uf

Theorem 2: A tree on n nodes has n-1 edges

Leaf - a node in a rooted tree, without children

Internal path - node in a rooted tree that isn’t a leaf

m-ary tree - each internal node has m children in this tree

Theorem 3 - An m-ary tree with i internal nodes has n≈mi+1 nodes

Corollary in an m-ary tree T

  • i internal nodes imply leaves
  •  leaves imply internal nodes and nodes
  • H nodes imply  internal nodes and  leaves

Height - length of longest path between root and leaf

Balanced tree - a rooted tree is a balanced ifall

                leaves are at level h or h-1 (within level in closeness)

Balanced                 Not balanced

Theorem 4: Let T be an m-ary tree of height h with l leaves;

  •  and if tree is balanced

             ↖          Symbols means you round up                        ↗

A tree with nodes  must have at least 2 nodes of degree 1

list - seen but unexplored nodes

S - starting node

        Put s on lit

        Mark s as seen

        While list contains node(s)

                Pick a node i from list

                If edge (i,j) exists with unseed node j

                        then mark j as seen

                        mark (i,j) as tree edge

                        put j on list

                Otherwise remove j from list

        This only finds all nodes if graph is connected

        “Tree edges” don't form circuits

Page Expired
5off
It looks like your free minutes have expired! Lucky for you we have all the content you need, just sign up here