Student Research Conference AbstractsMaria Areiz, Victor Danny Cardozo and Elvert RestrepoWhite Plains High SchoolDistance and Facility LocationSupervised by Lisa Gravitz We studied facility location problems in which we sought to find the best place to put a facility equally accessible to a number of people. By creating a graph we found that the center of a graph is the best place for such a facility since the center is the vertex or vertices that have minimum eccentricity. We studied various properties and theorems related to the center and pathcenter of trees and connected graphs. Mary Grace Bernardo and Loren de la CruzAcademy of Mount Saint UrsulaSupervised by Julia Davis If there is a distinct airport that only allows for three flights out,
passengers would want the shortest way (fewest connections) to get to
their destinations. For example, if there are 8 airports that are in
conjunction with each other, and a passenger would like to get to airport
6 from airport 3, there may be one path that would take three flights;
however, there may also be a direct flight to airport 6 from airport 3.
In this instance, the passenger would be wiser and more efficient to use
his time by taking the direct flight. However, the problem becomes more
complex when there are more than 8 airports. The goal of this project is
to find a formula that would find minimum amount of flights it would take
to get from one airport to another, considering that only three flights
are allowed in and out of each port. We hope to solve the problem by
making tables of the graphs of consecutive even number of ports until we
see a certain pattern that will help us discover a formula that will help
us if we have 100 or 1000 airports. Alex Cunha, and Danielle RosenbergWhite Plains High SchoolThe Traveling Salesman ProblemSupervised by Lisa Gravitz The Traveling Salesman Problem (TSP) is an optimization problem involving Hamilton Circuits. We studied four algorithms used for solving the TSP and analyzed the efficiency and efficacy of each algorithm. We also explored the TSP as an example of an NP - Complete problem. Alysha DaleyGrandview High SchoolSteiner Points and the Wizard of OzSupervised by Joanie Funderburk This presentation will introduce minimum spanning trees and how to
find them using Kruskal's Algorithm. The presentation will also include how
you can minimize the distance traveled if a Steiner point is introduced into
the problem. The presentation will demonstrate how using Torricelli's Method
can help in finding the Steiner point. Whitney Donaldson and Christine CordovaSan Marcos High SchoolSolving Shortest Path, Minimal Distance, and Traveling Salesman ProblemsUsing Weighted Graphs and Various Algorithms Supervised by Steve Wezniak Our graph theory research project, is titled "Solving Shortest Path, Minimal Distance, and Traveling Salesman Problems Using Weighted Graphs and Various Algorithms." We have done both internet and textbook research. In doing this we have found that by cross-referencing internet materials and textbook definitions we are better able to understand the information and present it in a less complex manner. Our project, a lesson plan to be taught to the class using overheads and practice problems, will contain basic definitions of key words and concepts pertaining to this field, as well as algorithms. The algorithms we will cover include: brute-force, nearest neighbor, cheapest link, and the approximate algorithm. We are also going to introduce formulas used to solve traveling salesman problems. Zak EdwardsEaglecrest High SchoolZookeeper's Dilemma:Using coloring to determine the least number of habitats to put animals in, some with a prey - predator relationship. Supervised by Erich Gott A zookeeper is given the charge of determining the least number of
habitats (cages) to house a certain number of animals. Some of these
animals cannot coexist. What is the least number of habitats to build so
that all animals can live peacefully? Linda Estevez and Lisa SchonbackThe Charter School of WilmingtonHarmonious and Line-Distinguishing ColoringSupervised by Dawn Vega In this presentation, we will be discussing formulas for solving line-distinguishing and harmonious coloring for paths, cycles, wheels, and complete bipartite graphs. To find the chromatic number for line-distinguishing coloring, you must know that this coloring is not proper, so two adjacent vertices can use the same color, but no two edges can have the same color class. For example: no two lines with a red vertex on one side and a blue one on the other. Harmonious coloring, which is a proper coloring, may not have two edges labeled with the same color class. Zach Hays Featherstone and Tyler Robert Riehle WykoffCentral Catholic Junior/Senior High SchoolDots and Boxes: A Winning StrategySupervised by Joyce Gates In this paper, we will be investigating winning strategies for the popular Dots and Boxes Game. We will be looking in to the strategies for different board sizes: two by two, three by three, four by four, etc. We will look into strategies against greedy types of players. Scott FrisonPort Allegany High SchoolDifferentiating Sets on n-CubesSupervised by Brian VanGorden This presentaion will include a discussion of differentiating sets of graphs. A brief explanation of differetniating sets will be given. Methods of placing detectors on n-cubes (specifically Q2, Q3, and Q4) and other graphs will be discussed. Aaron GroganCollegiate SchoolHarmonious Coloring of PathsSupervised by Laurie Rubel This presentation will explore the concept of harmonious coloring through
one of the most basic graph structures, the path. After a brief
introduction of paths and coloring, I will explain the specific objectives
of harmonious coloring. The path, inherently simple in form, will serve as
a good platform for initial investigation of harmonious coloring. An
interactive demonstration will allow attendees to absorb a solid
understanding of the harmonious coloring procedure. It will also
illustrate, however, the complex nature of harmonious coloring as graphs
get larger. The remainder of the presentation time will be used to both
tackle this complexity and show how aspects of the process can be
automated. I will show how I found one solution by algebraically
reproducing a pattern I saw. My presentation will conclude with an
overview of the related forms of harmonious coloring and will attempt to
relate it to some problems of the real world. Charles HeadCollegiate SchoolMinimizing the Total Distance of Three Regular GraphsSupervised by Laurie Rubel For any two vertices U and V in a graph, the distance d(U,V) is the number of edges of the shortest path between U and V. The total distance the graph is the sum of the distances from each vertex to every other vertex. I will demonstrate an algorithm to arrange the edges of three regular graphs to minimize the total distance of the graph. I will present the three regular graphs for n=8 and n=10 and use the algorithm to arrange these graphs. Ben HowardPort Allegany High SchoolHow Connected Are We?Supervised by Brian VanGorden This presentation includes discussion of designing and drawing a senior class connectedness graph. Related topics of cliques, cutsets, edge connectivity, and girth will also be presented with reference to the senior class graph. Justin LookOld Bridge High SchoolAcyclic Chromatic NumberSupervised by Dan Ilaria The acyclic chromatic number is a variation of the chromatic number of a graph. The method for coloring graphs to find the acyclic number will be discussed using specific graphs where conjectures were proven. Further results on other classes of graphs will be examined. Finally, a proof that shows a graph exists for any given combination of chromatic number and acyclic chromatic number. Royce S. OkuyamaThe Hill SchoolEquitable Chromatic Number of a Bipartite GraphSupervised by John Dollhopf In this talk we will review definitions and examples pertaining to
proper and equitable graph coloring. Our main result is the formula for the
equitable chromatic number of a bipartite graph. A sketch of the proof of
this result will be presented. Neal ParikhCollegiate SchoolFinding the k-level Domination Number for 2 x m GridsSupervised by Laurie Rubel (In collaboration with Savitar Sundaresan)Our project concerns finding the k-level domination number for 2 x m grids.
In k-level domination, one selects a random vertex, and all vertices k edges
away from that vertex are said to be dominated by that vertex. One then
continues selecting vertices until all the vertices of the graph are
dominated, and the minimum number of vertices required to dominate the
entire graph is called the domination number. Our goal is a formula for
finding the domination number d at level k for 2 x m grids. We have also
explored the domination numbers for l x m grids at 2, 3, and 4 level
domination. We discovered the maximum number of vertices that one vertex
could dominate with various levels of domination, and the figure that
represents the area that one vertex (or square) can dominate can be
tessellated to form a larger repeating pattern. From these patterns, we
attempted to derive a formula for 2, 3, and 4-level domination numbers in
l x m grids. Leo PerezHigh School of Telecommunications Arts and Sciencesk-Domination in Grid Graphs as it Relates to a Cooperative Learning SituationSupervised by Lorraine Lurie A dominating set S of vertices in a graph G is a subset of the vertices of G such that each vertex in G is in or adjacent to a vertiex in S. K-domination
extends this idea to allow the vertices in G to be at most k units apart from
a vertex in S. Applications to the theorems existing , developed and discussed in a paper written this summer at Dimacs by our team - Lorraine Lurie, Joanie Funderburk, Jennifer Schwartz - on "K-domination in Graphs" was explored by Leo Perez, who will be demonstrating and talking about his research on this topic. Hannah Portello-SwagelSitka High SchoolAlternative Voting Methods - A Closer LookSupervised by Dan Langbauer With all the mayhem that went on in Florida during this last presidential election, one wonders if an alternative voting system might actually be more fair and accurate than traditional plurality voting. Some alternatives inlcude approval voting, borda count, cumulative voting, and run-off voting, each with their own advantages and disadvantages. In 1948, economist Kenneth Arrow came up with some conditions that a "fair" voting system must meet, but later discovered that there can actually be no perfect voting system. I tested out his findings by carrying out my own voting simulation at my school using three of the voting methods. My contradicting results prove that the choice of which voting system used can greatly impact the outcome. Michael RobertsBethpage High SchoolGraph Theory DominationsSupervised by Christine Healy My topic is graphy theory dominations. It opens with an introduction
to graph theory then goes into what a domination is. Paul Dreyer's
work about Dominating the Roman empire is a large portion of my study.
It then branches into my own domination graph, a caterpillar. I then
show all different types of examples using the Roman model and the open
series. Jahvette Smidth and Sherry-Ann PetersCurtis High SchoolFire Detection in Curtis High SchoolSupervised by Nicole Vaiana We are looking for the minimum number of fire detectors we would need to
make our school safe from fires. Our detectors are able to detect fire in
the room in which they are placed as well as any room attached to it. By
creating a graph of our school we were able to use our research of placing
detectors on Paths to solve this problem. Ainie Soetanto and Jennifer GordonMarple Newtown Senior High SchoolBraces for Bridges and Buildings - Where and How Many?Supervised by Janice Ricks Modern day buildings and bridges are dependent on the strength and configuration of their steel girders. The fate of the structure lies in the rigidity of the joints. If the structure is braced properly, the joints will be rigid, and the structure will be able to withstand the effects of the "elements". Where and how should the braces be placed so the number of braces used is a minimum? Our objective is to find the optimum solution so that the structure is rigid but uses the least number of braces. Adam WaxmanBethpage High SchoolSteiner PointsSupervised by Christine Healy Steiner points are points placed within a figure to facilitate the creation
of the shortest possible connection between more than two points. The
actual connection of the points is called the Steiner Tree, and the Steiner
Tree is drawn by having three lines radiate out of each Steiner Point
(surrounding each point with three 120 degree angles) that connects either to
points of the figure or to other Steiner Points. The talk will begin with
an explanation of the way the use of Steiner Points helped Delta airlines
to reduce the cost of their phone lines between its three major offices.
After this a definition of Steiner Points will be presented and the manner
in which they can be placed within the regular polygons to make the
shortest possible connection of the points of the polygons will be shown.
During this explanation the fact that a 120 degree Steiner Tree is the shortest
possible connection of more than two points will be proven by using a
demonstration diagram. The formula that is used to determine how many
Steiner Points must be placed within a figure will be explained next
(N-2=the number of Steiner Points where N represents the number of sides of
the polygon). A relationship will be established between the ratio of the
length of the Steiner Tree to the perimeter of the polygon and the number
of sides of the polygon to establish the relationship between the number of
sides and the efficiency of the Steiner Tree. Soap bubbles, which are the
way in which Steiner Points are found in nature, will be discussed and will
lead into both an explanation and demonstration of Steiner Points in three
dimensions. The way in which Steiner Points are used in irregular polygons
will be briefly shown. Finally, the uses of Steiner Points, such as
shortening telephone wires, networking computers, setting up an intercom
system, and creating the shortest possible routes (for golf courses and
ambulances), will be discussed along with the irregularities that arise
when Steiner Points are used in the real world (fractal arrays, physical
obstacles, a taxicab plane, and collinear points). |