High School Student Research Conference 2003 Abstracts White Plains High School, White Plains, NY Three Door Entrance Problem Supervised by Lisa Weber, DCI 2000 In this problem our group had to decide if the 3 entrance doors chosen by the school administration allowed the students to get to class with the shortest average distance. We thought this would be a good problem to choose because if we come up with a better solution to this problem, it might be taken into consideration by the principal. We created a graph that modeled the entire building and plotted every classroom on it. We found mathematically that the 3 doors chosen by the school were not the most efficient ways to get to class for all students. We recommend there should be more doors that allow students to enter the building. There are buildings that have a long distance between the entrance doors chosen by the school, which does not allow for the shortest average distance.
Seton Catholic High School, Pittston, PA Comparing Algorithms for Searching Graphs Using C++ Supervised by James Kupetz, DCI 2002 Let n be the number of vertices and e be the number of edges in a graph G.
G can be represented in a twodimensional format or a onedimensional format. We compare the efficiency of these two formats as n increases. We also formulate different algorithms for searching for triangles in G and compare the speed of these algorithms as n and e increase.
White Plains High School, White Plains, NY Restaurant Dilemma Supervised by Lisa Weber, DCI 2000 When a restaurant owner comes to White Plains they? re faced with the problem of where the restaurant should be located. The location and distance of the students? houses helps them determine where to place the restaurants. Our project consisted of plotting the houses of each student to help find the best location for each restaurant. The houses were plotted as vertices. To connect the houses to one another we plotted vertices at all intersections. The location of the vertices determined the distance between the restaurants and the houses. We then plotted bus stops and a bus route, again considering all intersections as vertices. We found that even if we place the restaurants close to one another they may have the same number of customers because the students live so far apart from one another. The graph would help a restaurant owner determine the distances from their restaurants to each of the houses, making it easier to decide on a location.
Upper Township Middle School, Petersburg, NJ The Ins and Outs of Guarding the Art Supervised by Dolores Endicott, DCI 2002 We considered how to guard an art gallery using vertex guards. We found the shape that for any given number of sides required the most number of guards. Using this shape a table was developed to show the relationship between the number of sides in the shape and the number of guards that were always sufficient and sometimes necessary to guard the figure. The pattern shown in the table aided us in discovering a formula that would give us this number of guards. Our task was then to determine the most efficient way to place the guards. We first did this for polygonal shapes then extended this to more specific shapes like orthogonal ones. We considered vertex guards that were guarding the inside and vertex guards that were guarding the outside of our figures. By comparing theses findings we were able to make a few generalizations.
Kennedy Catholic High School, Hermitage, PA Orcs, Goblins, and Trolls, Oh My! The Domination of Middle Earth Supervised by Janelle Stufft, DCI 2002 This presentation will focus on step domination. We define step domination as domination of a graph where each vertex is dominated by a vertex of strength k at most k edges away. In our project, k can equal 1,2,3, or 4. We have used a map of Middle Earth from J.R.R. Tolkien's The Lord of the Rings and developed 3 subgraphs from it. In order to do this we took the major cities of Middle Earth and made them vertices. Then we considered the different peoples of Middle Earth, such as elves, and calculated the strength of each group (army). We then dominated each subgraph by using step domination as defined above. In addition, we combined the subgraphs to reach our ultimate goal, domination of Middle Earth.
The Charter School of Wilmington, DE Exploiting the Senior Class Supervised by Chuck Biehl, DCI Lead Teacher Inspired by recent work by James Abello of DIMACS on massive graph
mining, we constructed a weighted acquaintance graph for the senior
class at the Charter School of Wilmington, using edge weights to
quantify the strength of friendships. We iteratively contracted the
graph to try to identify superior and inferior weighted cliques. Our
goal is to contract the graph to produce a weighted forest from which we
hope to be able to exploit the entire graph based on identifying who the
major influences are in the school.
University of Vermont Scheduling Tournaments and Leagues The talk will survey some of the problems that come up when you have
to schedule a tournament or a league. Although there are standard
solutions that go by the name "combinatorial designs," the real
world (e.g., your mother's golf tournament) often presents additional
considerations and constraints that lead to interesting problems. In
this talk we will discuss how one might construct a round robin
tournament. We will then survey some known results on tournaments that
satisfy additional balance conditions.
(Presentation via video tape) Livingston High School, Livingston, NJ How well connected is the Senior Class at Livingston High School Supervised by David Hyman, DCI 2002 By using a simple survey and graph theory and , how can you tell the
level of connectedness of a population of people. What useful
information can be drawn from the graphs that can benefit the school
and community.
The International High School @LGCC, LIC, NY Radio Frequency Assignment Supervised by Persheen Maxwell, DCI 2002 We used vertex labeling to assign frequencies to radio stations that had overlapping broadcast areas. When these areas overlap, there is interference where the overlap takes place. We used graph labeling to solve the problems of overlapping frequencies.
White Plains High School, White Plains, NY Konigsberg Bridge Problem Supervised by Christine Spatola, DCI 2002 My research project focuses on the Konigsberg Bridge Problem, in particular, Euler paths and circuits. My research focuses on various algorithms and theories that will help support my project.
The International High School @LGCC, LIC, NY Polyhedra Coloring Supervised by Persheen Maxwell, DCI 2002 We used vertex, edge, and region coloring to try to determine the minimum number of colors need to color the Regular Polyhedra. We then considered how this would change if we included the truncated version of the regular polyhedra. The regular polyhedra are Tetrahedron, Hexahedron, Octahedron, Dodecahedron and the Icosahedron.
White Plains High School, White Plains, NY Scheduling Abstract Supervised by Christine Spatola, DCI 2002 We completed the Scheduling project that involved the FIFA 2002 World Cup and the connection to the concept of directed graphs in graph theory.
The International High School @LGCC, LIC, NY Optimizing Networks (Traveling Salesperson Problem) Supervised by Persheen Maxwell, DCI 2002 Optimizing networks is to find the most efficient routes through networks. We used the idea of spanning trees and circuits to investigate networks and the traveling salesperson problem in hopes of finding the most efficient route.
DobynsBennett High School, Kingsport, TN The Olympic Ring Problem Supervised by Tara Harrell, DCI 2002 In this presentation, we consider the Olympic Ring Problem, proposed by the
University of Sydney, Australia in the year 2000. The problem involves labeling the regions of the Olympic Games' Rings with consecutive nonrepeating natural numbers. These labels should be allocated in a way that any circle contains a constant sum. We pose a system for labeling odd paths. As well as showing specific graphs that have no labeling. Suggestions for further research are given.
DobynsBennett High School, Kingsport, TN Finding the Search Number of a Graph Supervised by Tara Harrell, DCI 2002 In this presentation, we consider finding the search number of a graph. We will define search number, as well as identify the search number of various graphs. Such results include paths, cycles, stars, fans, wheels, and trees. Suggestions for further research will be given.
White Plains High School, White Plains, NY Abstract for Domination : Video Camera Surveillance Supervised by Christine Spatola, DCI 2002 In this group we chose to complete the project on Domination: Video Cameras Surveillance of White Plains High School. We had to determine every spot a camera should be placed in the building so that there are no gaps in the surveillance of the building. This research was done so that if the White Plains High School were to need cameras placed in the building, we would already know or have a general idea of where the cameras should be placed and how many should be set up.
